제출 #1198490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198490		kevinyang	Feast (NOI19_feast)	C++20	100 / 100	879 ms	23916 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,k;
    cin >> n >> k;
    vector<int>a(n+1);
    for(int i = 1; i<=n; i++){
        cin >> a[i];
    }
    auto aliens = [&](int lambda) -> pii {
        vector<vector<pii>>dp(n+1,vector<pii>(2));
        dp[0][1] = {-(int)1e18,0};
        for(int i = 1; i<=n; i++){
            dp[i][1] = max(pii{dp[i-1][0].first+a[i]-lambda,dp[i-1][0].second+1},pii{dp[i-1][1].first+a[i],dp[i-1][1].second});
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
        }
        return max(dp[n][0],dp[n][1]);
    };
    int low = -1; int high = (int)1e18;
    while(low + 1 < high){
        int mid = (low+high)/2;
        auto [cost,used] = aliens(mid);
        if(used <= k){
            high = mid;
        }
        else{
            low = mid;
        }
    }
    auto [cost,used] = aliens(high);
    //cout << cost << ' ' << used << ' ' << high << '\n';
    cout << cost + k * high << '\n';
    return 0;
}

• 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