oj.uz

Submission #1102923

# Submission time Handle Problem Language Result Execution time Memory
1102923 2024-10-19T08:52:32 Z alexdumitru Feast (NOI19_feast) C++17
12 / 100
 157 ms 8576 KB 
#include <iostream>

using ll = int64_t;

const int NMAX = 3e5;

int n, k;
int a[NMAX + 1];
ll sp[NMAX + 1];
ll ans;


void read() {
    std::cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        sp[i] = sp[i - 1] + a[i];
    }
}

std::pair<ll, int> dp[NMAX + 1];

bool operator < (const std::pair<ll, int> & a, const std::pair<ll, int> & b) {
    if (a.first != b.first)
        return a.first < b.first;
    return a.second > b.second;
}

bool operator > (const std::pair<ll, int> & a, const std::pair<ll, int> & b) {
    if (a.first != b.first)
        return a.first > b.first;
    return a.second < b.second;
}

std::pair<ll, int> operator + (const std::pair<ll, int> & a, const std::pair<ll, int> & b) {
    return std::make_pair(a.first + b.first, a.second + b.second);
}

std::pair<ll, int> my_max(const std::pair<ll, int> & a, const std::pair<ll, int> & b) {
    return a > b ? a : b;
}

std::pair<ll, int> ok(ll pen) {
    int idx = 0;
    for (int i = 1; i <= n; i++) {
        //dp[i] = dp[j] + sp[i] - sp[j]
        dp[i] = my_max(dp[i - 1], dp[idx] + std::make_pair(sp[i] - sp[idx] - pen, 1));
        if (dp[i] + std::make_pair(-sp[i], 0) > dp[idx])
            idx = i;
    }
    return dp[n];
}

void solve() {
    ll st = 1;
    ll dr = 3e14;
    while (st <= dr) {
        ll mij = (st + dr) / 2;
        auto v = ok(mij);
        if (v.second <= k) {
            ans = v.first + mij * v.second;
            dr = mij - 1;
        } else {
            st = mij + 1;
        }
    }
}

void write_ans() {
    std::cout << ans << '\n';
}

int main() {
    read();
    solve();
    write_ans();
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8224 KB Output is correct
2 Correct 145 ms 8532 KB Output is correct
3 Correct 151 ms 8576 KB Output is correct
4 Correct 157 ms 8520 KB Output is correct
5 Correct 145 ms 8524 KB Output is correct
6 Correct 135 ms 8264 KB Output is correct
7 Correct 135 ms 8264 KB Output is correct
8 Correct 138 ms 8524 KB Output is correct
9 Correct 135 ms 8264 KB Output is correct
10 Correct 138 ms 8436 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 8336 KB Output is correct
2 Correct 101 ms 8520 KB Output is correct
3 Correct 113 ms 8312 KB Output is correct
4 Correct 103 ms 8264 KB Output is correct
5 Correct 135 ms 8264 KB Output is correct
6 Correct 98 ms 8236 KB Output is correct
7 Correct 111 ms 8520 KB Output is correct
8 Correct 138 ms 8520 KB Output is correct
9 Correct 134 ms 8204 KB Output is correct
10 Correct 101 ms 8508 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 8528 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 336 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 336 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 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8224 KB Output is correct
2 Correct 145 ms 8532 KB Output is correct
3 Correct 151 ms 8576 KB Output is correct
4 Correct 157 ms 8520 KB Output is correct
5 Correct 145 ms 8524 KB Output is correct
6 Correct 135 ms 8264 KB Output is correct
7 Correct 135 ms 8264 KB Output is correct
8 Correct 138 ms 8524 KB Output is correct
9 Correct 135 ms 8264 KB Output is correct
10 Correct 138 ms 8436 KB Output is correct
11 Correct 95 ms 8336 KB Output is correct
12 Correct 101 ms 8520 KB Output is correct
13 Correct 113 ms 8312 KB Output is correct
14 Correct 103 ms 8264 KB Output is correct
15 Correct 135 ms 8264 KB Output is correct
16 Correct 98 ms 8236 KB Output is correct
17 Correct 111 ms 8520 KB Output is correct
18 Correct 138 ms 8520 KB Output is correct
19 Correct 134 ms 8204 KB Output is correct
20 Correct 101 ms 8508 KB Output is correct
21 Incorrect 137 ms 8528 KB Output isn't correct
22 Halted 0 ms 0 KB -