Compy's Blog
224 words
1 minutes
[BOJ] 연세워터파크
2025-04-05

연세워터파크

TimeLimitMemoryLimitConditionTAG
1s128MB(2 ≤ N ≤ 100000
1 ≤ D ≤ N-1)
Dynamic Programming

그냥 전형적인 DP인데 약간 새로운 관리법이 추가된 dp? 느낌이네요. 생각보다 재밌는 문제였습니다.

한번씩 풀어보면 좋을 듯 합니다.

정답 코드
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
using ll = long long;
int n, d;
ll dp[100'001];
ll nums[100'001];
map<ll, ll> current;
set<ll> keys;

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

    
    cin >> n >> d;
    ll result = -1e10;
    for(int i = 0; i < n; i++) cin >> nums[i];
    
    for(int i = 0; i < d; i++){
        ll previous = keys.empty() ? 0 : *--keys.end();
        dp[i] = max(previous + nums[i], nums[i]);
        
        keys.insert(dp[i]);
        current[dp[i]]++;
        
        result = max(dp[i], result);

    }
    for(int i = d; i < n; i++){
        ll previous = *--keys.end(); // 일단 전에 있던 것들 중에서 올 수 있는 가장 쩌는 애를 데려오겟다ㅓ
        dp[i] = max(previous + nums[i], nums[i]);
        
        keys.insert(dp[i]);
        current[dp[i]]++;
        
        
        current[dp[i - d]] --;
        if(!current[dp[i - d]]) keys.erase(dp[i-d]);
        
        result = max(dp[i], result);
    }
    
    
    cout << result;

    
    

    return 0;
}
[BOJ] 연세워터파크
https://compy07.github.io/Blog/posts/boj/15678/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-04-05