목록누적 합 (3)
레야몬

1. 문제 1번부터 n번까지 번호가 붙여진 병사가 있다. 지휘관은 번호가 연속하도록 여러 특공대를 나눈다. 각 병사의 전투력은 \(x_i\)이며 이들로 구성된 특공대의 각 병사 전투력 합이 x라고 할 때 이 특공대의 전투력은 \(ax^2+bx+c\)이다. \((a < 0)\). 각 특공대의 전투력의 합의 최댓값을 구하시오. -1- 전체 병사 수 \(n(1 \leq n \leq 1,000,000)\) -1- 세 정수 a, b, c \((-5 \leq a \leq -1, \left| b \right| \leq 10,000,000, \left| c \right| \leq 30,000,000)\) -1- \(x_1, x_2, ..., x_n (1 \leq x_i \leq 100)\) -1- 각 특공대의 전투력 ..
1. 문제 수열 \(A_{i}\)가 주어진다. 연속된 부분 구간의 합이 M으로 나눠지는 구간의 개수를 구하여라 - 1 - \(N, M(1 \leq N 10^{6}, 2 \leq M \leq 10^{3})\) - 2 - \(A_{i}(0 \leq A_{i} \leq 10^{9})\) 연속된 부분 구간의 합이 M으로 나눠 떨어지는 구간의 개수를 출력한다. 2. 재정의 \(A_{i} + ... + A_{j} (i \leq j)\)의 합이 M으로 나누어 떨어지는 \((i, j)\)쌍의 개수 출력 3. 해결 방법 두 구간의 나머지가 M으로 같다면 두 구간의 합의 차의 나머지는 0이다. 즉 이를 이용해 누적합의 차가 k가 되는 구간(0, i)의 개수를 remain[k]에 저장하고 나서 kC2와 remain[0]을 ..
#include #define MAX_SIZE 1025 using namespace std; int N, M; //표의 크기 N, 합을 구해야 하는 횟수 M int x1, y1, x2, y2; int memo[MAX_SIZE][MAX_SIZE]; //메모리제이션 누적합 int map[MAX_SIZE][MAX_SIZE]; //맵 int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for(int i=1; i map[i][j]; sum+=map[i][j]; memo[i][j] = memo[i-1][j]+sum; //(0, 0)에서 (x, y)까지의 누적합 } } for(int i=0; i> x1 ..