제출 #1229142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229142		Adomas08	Feast (NOI19_feast)	C++20	100 / 100	116 ms	12168 KiB

feast

#include <bits/stdc++.h>

using namespace std;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    long long a[n+1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    long long s = 0, e = 3 * 1e14;
    pair<long long, int> dp[n+1][2];
    while (s != e){
        long long m = (s + e+1) / 2;
        dp[0][0] = {0, 0};
        dp[0][1] = {LLONG_MIN, LLONG_MIN};
        for (int i = 1; i <= n; i++){
            if (dp[i-1][0].first > dp[i-1][1].first){
                dp[i][0] = dp[i-1][0];
            }
            if (dp[i-1][0].first < dp[i-1][1].first){
                dp[i][0] = dp[i-1][1];
            }
            if (dp[i-1][0].first == dp[i-1][1].first){
                dp[i][0] = {dp[i-1][0].first, max(dp[i-1][0].second, dp[i-1][1].second)};
            }
            if (dp[i-1][0].first - m > dp[i-1][1].first){
                dp[i][1] = {dp[i-1][0].first + a[i] - m, dp[i-1][0].second + 1};
            }
            if (dp[i-1][0].first - m < dp[i-1][1].first){
                dp[i][1] = {dp[i-1][1].first + a[i], dp[i-1][1].second};
            }
            if (dp[i-1][0].first - m == dp[i-1][1].first){
                dp[i][1] = {dp[i-1][1].first + a[i], max(dp[i-1][0].second + 1, dp[i-1][1].second)};
            }
        }
        long long amo;
        if (dp[n][0].first > dp[n][1].first){
            amo = dp[n][0].second;
        }
        if (dp[n][0].first < dp[n][1].first){
            amo = dp[n][1].second;
        }
        if (dp[n][0].first == dp[n][1].first){
            amo = max(dp[n][1].second, dp[n][0].second);
        }
        if (amo < k){
            e = m - 1;
        }
        else{
            s = m;
        }
    }
    long long m = s;
    dp[0][0] = {0, 0};
    dp[0][1] = {LLONG_MIN, LLONG_MIN};
        for (int i = 1; i <= n; i++){
            if (dp[i-1][0].first > dp[i-1][1].first){
                dp[i][0] = dp[i-1][0];
            }
            if (dp[i-1][0].first < dp[i-1][1].first){
                dp[i][0] = dp[i-1][1];
            }
            if (dp[i-1][0].first == dp[i-1][1].first){
                dp[i][0] = {dp[i-1][0].first, max(dp[i-1][0].second, dp[i-1][1].second)};
            }
            if (dp[i-1][0].first - m > dp[i-1][1].first){
                dp[i][1] = {dp[i-1][0].first + a[i] - m, dp[i-1][0].second + 1};
            }
            if (dp[i-1][0].first - m < dp[i-1][1].first){
                dp[i][1] = {dp[i-1][1].first + a[i], dp[i-1][1].second};
            }
            if (dp[i-1][0].first - m == dp[i-1][1].first){
                dp[i][1] = {dp[i-1][1].first + a[i], max(dp[i-1][0].second + 1, dp[i-1][1].second)};
            }
        }
    cout << s * k + max(dp[n][0].first, dp[n][1].first);
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29