https://www.acmicpc.net/problem/2559
2559: 서열
첫 번째 줄에는 N과 K라는 두 개의 정수가 순서대로 공백을 두고 포함되어 있습니다. 첫 번째 정수 N은 온도가 측정된 총 일수입니다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합계
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int n, k,temp; //숫자, 연속일
int psum(100001);
int ret = -10000004; //최악의경우 : -100*10만번(n)
/*
* (-) 이중포문 : 100,000 * 100,000 ->시간초과
*
* 해결 :
* 구간쿼리는 psum!!!!!!!!!
* ex)
* 배열 : 1 2 3 4 5
* psum : 1 3 6 10 15
*
* for문은 i=k~n으로 돌리면됨.
* ret=max(ret,p(i)-p(i-k))
* ex) psum(3)-psum(3-3)
*/
int main()
{
cin >> n >> k;
/*
* a배열에 넣을필요없음. 바로temp로 덧셈
*
*/
for (int i = 1; i <= n; ++i) {
cin >> temp; psum(i) = psum(i - 1) + temp;
}
/*
* n=5(1,2,3,4,5)
* k=3
* idx: 0 1 2 3 4 5(n)
* psum : 0 1 3 6 10 15
*
* i=3~5
* psum(3)-psum(3-3)
* psum(4)-p(4-3)
* psum(5)-p(5-3)
*/
for (int i = k; i <= n; i++) {
ret = max(ret, psum(i) - psum(i - k));
}
cout << ret;
}
이해가 안되면 외우자.