Submission #587698

#	Time	Username	Problem	Language	Result	Execution time	Memory
587698		Derzeed	Feast (NOI19_feast)	C++14	0 / 100	48 ms	5580 KiB

feast

#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define com complex<double>
#define ld long double;
#define ii pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vc vector<char>
#define vs vector<string>
#define vd vector<double>
#define vcom vector<com>
#define vld vector<ld>
#define vll vector<ll>
#define vvi vector<vi>
#define vvii vector<vii>
#define vvc vector<vc>
#define vvs vector<vs>
#define vvll vector<vll>
#define vvd vector<vd>
#define vvcom vector<vcom>
#define vvld vector<vld>
#define FOR(x,n) for(int x=0;x<(n);x++)
#define FORS(x,n) for(int x=1;x<=(n);x++)
#define FORE(x,a) for(auto &x: a)
#define FORT(x,a,b) for(int x=(a);x<(b);x++)
#define FORD(x,a,b) for(int x=(a);x>=(b);x--)
#define ALL(x) x.begin(),x.end()
#define REP(n) for(int _ = 0; _ < n; _++)
#define MT make_tuple
#define MP make_pair
#define pb push_back
#define endl '\n'
#define F first
#define S second
#define vvvll vector<vvll>
#define sz(x) ((int)x.size())

pair<ll,ll> relax(int p, vll &a) {
    int n = a.size();
    int cv = 0; // curval
    int cb = 0; // curbest

    int t = 0, cnt = 0;

    FOR(i,n) {
        cv += a[i];
        if(cv <= cb-p && cb > p) {
            cnt += 1;
            t += cb-p;
            cv = 0;
            cb = 0;
        } else {
            cb = max(cb,cv);
            if(cv < 0) {
                cv = 0;
            }
        }
    }
    if(cb > p) {
        cnt += 1;
        t += cb-p;
        cv = 0;
    }
    return {t,cnt};
}

void solve() {
    int n,k; cin >> n >> k;
    vll a(n);
    FOR(i,n) cin >> a[i];

    int cp = 0;
    ll pv = 0;
    FOR(i,n) {
        if(a[i] > 0) {
            cp++;
            pv += a[i];
        }

    }

    if(cp <= k) {
        cout << pv << endl;
        return;
    }

    ll mi = 0, ma = 2e9;
    while(mi < ma ){
        ll t,cnt;
        ll mid = (mi+ma)/2;
        tie(t,cnt) = relax(mid,a);
        cout << mid << " " << t << " " << cnt << endl;
        if(cnt <= k) {
            ma = mid;
        } else {
            mi = mid + 1;
        }
    }

    ll t,cnt;
    tie(t,cnt) = relax(mi,a);
    cout << t + cnt*mi << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;

    while(t--) {
        solve();
    }
}

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