oj.uz

Submission #587701

# Submission time Handle Problem Language Result Execution time Memory
587701 2022-07-02T08:52:53 Z Derzeed Feast (NOI19_feast) C++14
0 / 100
 49 ms 5324 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 2516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2516 KB Output is correct
2 Correct 33 ms 3816 KB Output is correct
3 Correct 30 ms 3656 KB Output is correct
4 Correct 31 ms 3660 KB Output is correct
5 Incorrect 49 ms 5324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 2516 KB Output isn't correct
2 Halted 0 ms 0 KB -