oj.uz

Submission #1025978

# Submission time Handle Problem Language Result Execution time Memory
1025978 2024-07-17T12:09:38 Z Zicrus Feast (NOI19_feast) C++17
12 / 100
 123 ms 5700 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, k;
vector<ll> a;

pair<ll, ll> solve(ll p) {
    ll dp = 0;
    ll dpSeg = a[0];
    ll ps = 0;
    ll psSeg = 1;
    for (int i = 1; i < n; i++) {
        ps = (dp - ps * p) > (dpSeg - psSeg * p) ? ps : psSeg;
        dp = (dp - ps * p) > (dpSeg - psSeg * p) ? dp : dpSeg;
        if (dp - ((ps+1) * p) > dpSeg) {
            dpSeg = dp - p + a[i];
            psSeg = ps + 1;
        }
        else {
            dpSeg += a[i];
        }
    }
    ll val = (dp - ps * p) > (dpSeg - psSeg * p) ? (dp - ps * p) : (dpSeg - psSeg * p);
    ll pss = dp == dpSeg ? min(ps, psSeg) : (dp > dpSeg ? ps : psSeg);
    return {val, pss};
}

int main() {
    cin >> n >> k;
    a = vector<ll>(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ll l = 0, r = 1ll << 50;
    ll bestK = 1ll << 50;
    while (l < r) {
        ll mid = (l + r) / 2;
        bestK = solve(mid).second;
        if (bestK > k) {
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }
    auto s = solve(l);
    ll val = solve(l).first + k * l;
    cout << val;
}

Compilation message

feast.cpp: In function 'int main()':
feast.cpp:49:10: warning: variable 's' set but not used [-Wunused-but-set-variable]
   49 |     auto s = solve(l);
      |          ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 5456 KB Output is correct
2 Correct 90 ms 5456 KB Output is correct
3 Correct 95 ms 5456 KB Output is correct
4 Correct 93 ms 5552 KB Output is correct
5 Correct 91 ms 5456 KB Output is correct
6 Correct 97 ms 5456 KB Output is correct
7 Correct 91 ms 5456 KB Output is correct
8 Correct 99 ms 5436 KB Output is correct
9 Correct 92 ms 5380 KB Output is correct
10 Correct 91 ms 5412 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3608 KB Output is correct
2 Correct 59 ms 3676 KB Output is correct
3 Correct 59 ms 3672 KB Output is correct
4 Correct 63 ms 3620 KB Output is correct
5 Correct 97 ms 5460 KB Output is correct
6 Correct 61 ms 3608 KB Output is correct
7 Correct 64 ms 3676 KB Output is correct
8 Correct 96 ms 5436 KB Output is correct
9 Correct 103 ms 5376 KB Output is correct
10 Correct 66 ms 3672 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 5456 KB Output is correct
2 Correct 90 ms 5456 KB Output is correct
3 Correct 95 ms 5456 KB Output is correct
4 Correct 93 ms 5552 KB Output is correct
5 Correct 91 ms 5456 KB Output is correct
6 Correct 97 ms 5456 KB Output is correct
7 Correct 91 ms 5456 KB Output is correct
8 Correct 99 ms 5436 KB Output is correct
9 Correct 92 ms 5380 KB Output is correct
10 Correct 91 ms 5412 KB Output is correct
11 Correct 56 ms 3608 KB Output is correct
12 Correct 59 ms 3676 KB Output is correct
13 Correct 59 ms 3672 KB Output is correct
14 Correct 63 ms 3620 KB Output is correct
15 Correct 97 ms 5460 KB Output is correct
16 Correct 61 ms 3608 KB Output is correct
17 Correct 64 ms 3676 KB Output is correct
18 Correct 96 ms 5436 KB Output is correct
19 Correct 103 ms 5376 KB Output is correct
20 Correct 66 ms 3672 KB Output is correct
21 Incorrect 123 ms 5700 KB Output isn't correct
22 Halted 0 ms 0 KB -