(백준/c++) 2559 - 수열

2559번: 수열 (acmicpc.net)

2559번: 수열

누적 합

 

* 가장 큰 값만 찾기 때문에 priority_queue 사용함.(기본 정렬 = less)

* S값보다 크거나 같을 때부터 누적 합을 해주어 queue에 넣어줌.

#include<iostream>
#include<stdlib.h>
#include<queue>
#include<memory.h>
using namespace std; 
#define MAX 100'001
int SumArr[MAX], Arr[MAX];
// 구간 합. 

int main(void)
{
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);

    int N, S; 
    priority_queue<int> pq;
    cin >> N >> S;
    memset(SumArr, 0, sizeof(SumArr));
    memset(Arr, 0, sizeof(Arr));

    for(int i=1; i<=N; ++i)
    {
        cin>>Arr[i]; 
        SumArr[i]=Arr[i]+SumArr[i-1];
        if(i>=S)
        {
            pq.emplace(SumArr[i]-SumArr[i-S]);
        }
    }

    cout << pq.top(); 
    
    return 0;
}