Submission #697771

#	Time	Username	Problem	Language	Result	Execution time	Memory
697771		minhnhatnoe	Feast (NOI19_feast)	C++17	100 / 100	158 ms	11596 KiB

feast

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> a;
vector<ll> pf;
pair<ll, int> solve(ll cost){
    vector<pair<ll, int>> dp(a.size());
    pair<ll, int> maxval(0, 0);
    for (int i=0; i<a.size(); i++){
        dp[i] = max(i ? dp[i-1] : make_pair(0LL, 0),
                    make_pair(pf[i] - cost + maxval.first, maxval.second + 1));
        maxval = max(maxval, make_pair(-pf[i] + dp[i].first, dp[i].second));
    }
    return dp.back();
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, k; cin >> n >> k;
    a.resize(n);
    for (int i=0; i<n; i++) cin >> a[i];
    pf.resize(n);
    for (ll i=0, p=0; i<n; i++){
        p = pf[i] = p + a[i];
    }
    ll bl = 0, br = 1e15;
    while (bl < br){
        ll bm = (bl + br)>>1;
        pair<ll, int> r = solve(bm);
        if (r.second <= k) br = bm;
        else bl = bm+1;
    }
    pair<ll, int> r = solve(bl);
    cout << r.first + bl*r.second << "\n";
}

Compilation message (stderr)

feast.cpp: In function 'std::pair<long long int, int> solve(ll)':
feast.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~

• 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