oj.uz

Submission #875111

# Submission time Handle Problem Language Result Execution time Memory
875111 2023-11-18T17:04:05 Z rakkoon69 Feast (NOI19_feast) C++17
30 / 100
 77 ms 8124 KB 
#include <bits/stdc++.h>

#define int long long
#define ll long long
#define II pair<int, int>
#define fs first
#define sc second
#define endl '\n'

#define mp(x, y) make_pair(x, y)
#define sz(x) ((int) (x.size()))
#define forlr(i, l, r) for(int i = l; i <= r; ++i)
#define forrl(i, r, l) for(int i = r; i >= l; --i)
#define show(v) for(auto i : v) cout << i << " "; cout << endl;
#define showlr(v, l, r) for (int i = l; i <= r; i++) cout << v[i] << " "; cout << endl;
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end());

const long long LINF = 1ll << 60;
const int INF = 1 << 30;
const int N = 3e5 + 5;

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 

int n, k;
int a[N], p[N];

II choose(II A, II B) {
    if(A.fs == B.fs) return A.sc < B.sc ? A : B;
    return A.fs > B.fs ? A : B;    
}

II calc(int cost) {
    II take = {0, 0}, best = {0, 0};

    forlr(i, 1, n) {
        best = choose(best, {take.fs + p[i] - cost, take.sc + 1});
        take = choose(take, {best.fs - p[i], best.sc});
    }

    return best;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> k;

    forlr(i, 1, n) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }

    int ans = -1e14;
    int lo = -1e9, hi = 3e14;
    while(lo <= hi) {
        int mid = (lo + hi) >> 1;
        II v = calc(mid);

        if(v.sc > k) lo = mid + 1;
        else hi = mid - 1, ans = v.fs + k * mid;
    }

    cout << ans << endl;

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7804 KB Output is correct
2 Correct 68 ms 7968 KB Output is correct
3 Correct 71 ms 8020 KB Output is correct
4 Correct 70 ms 8000 KB Output is correct
5 Correct 68 ms 7760 KB Output is correct
6 Correct 67 ms 7772 KB Output is correct
7 Correct 67 ms 7764 KB Output is correct
8 Correct 70 ms 8016 KB Output is correct
9 Correct 69 ms 7888 KB Output is correct
10 Correct 68 ms 7760 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6204 KB Output is correct
2 Correct 61 ms 6276 KB Output is correct
3 Correct 59 ms 6144 KB Output is correct
4 Correct 60 ms 6236 KB Output is correct
5 Correct 71 ms 7876 KB Output is correct
6 Correct 59 ms 6192 KB Output is correct
7 Correct 62 ms 6232 KB Output is correct
8 Correct 72 ms 8000 KB Output is correct
9 Correct 67 ms 7860 KB Output is correct
10 Correct 60 ms 6256 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8028 KB Output is correct
2 Correct 73 ms 7916 KB Output is correct
3 Correct 73 ms 8124 KB Output is correct
4 Correct 70 ms 8064 KB Output is correct
5 Correct 77 ms 8028 KB Output is correct
6 Correct 71 ms 8060 KB Output is correct
7 Correct 71 ms 8028 KB Output is correct
8 Correct 74 ms 8056 KB Output is correct
9 Correct 71 ms 8072 KB Output is correct
10 Correct 72 ms 7932 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7804 KB Output is correct
2 Correct 68 ms 7968 KB Output is correct
3 Correct 71 ms 8020 KB Output is correct
4 Correct 70 ms 8000 KB Output is correct
5 Correct 68 ms 7760 KB Output is correct
6 Correct 67 ms 7772 KB Output is correct
7 Correct 67 ms 7764 KB Output is correct
8 Correct 70 ms 8016 KB Output is correct
9 Correct 69 ms 7888 KB Output is correct
10 Correct 68 ms 7760 KB Output is correct
11 Correct 60 ms 6204 KB Output is correct
12 Correct 61 ms 6276 KB Output is correct
13 Correct 59 ms 6144 KB Output is correct
14 Correct 60 ms 6236 KB Output is correct
15 Correct 71 ms 7876 KB Output is correct
16 Correct 59 ms 6192 KB Output is correct
17 Correct 62 ms 6232 KB Output is correct
18 Correct 72 ms 8000 KB Output is correct
19 Correct 67 ms 7860 KB Output is correct
20 Correct 60 ms 6256 KB Output is correct
21 Correct 70 ms 8028 KB Output is correct
22 Correct 73 ms 7916 KB Output is correct
23 Correct 73 ms 8124 KB Output is correct
24 Correct 70 ms 8064 KB Output is correct
25 Correct 77 ms 8028 KB Output is correct
26 Correct 71 ms 8060 KB Output is correct
27 Correct 71 ms 8028 KB Output is correct
28 Correct 74 ms 8056 KB Output is correct
29 Correct 71 ms 8072 KB Output is correct
30 Correct 72 ms 7932 KB Output is correct
31 Correct 1 ms 2392 KB Output is correct
32 Incorrect 0 ms 2396 KB Output isn't correct
33 Halted 0 ms 0 KB -