oj.uz

Submission #1102948

# Submission time Handle Problem Language Result Execution time Memory
1102948 2024-10-19T09:12:54 Z alexdumitru Feast (NOI19_feast) C++17
12 / 100
 129 ms 9808 KB 
#include <iostream>


using ll = int64_t;
#define int ll

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> ok(ll pen) {
    int idx = 0;
    for (int i = 1; i <= n; i++) {
        //dp[i] = dp[j] + sp[i] - sp[j]
        dp[i] = std::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 = 0;
    ll dr = 3e14;
    while (st <= dr) {
        ll mij = (st + dr) / 2;
        auto v = ok(mij);
        if (v.second > k) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    ans = ok(st).first + st * k;
}

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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 9548 KB Output is correct
2 Correct 122 ms 9484 KB Output is correct
3 Correct 123 ms 9716 KB Output is correct
4 Correct 128 ms 9544 KB Output is correct
5 Correct 129 ms 9544 KB Output is correct
6 Correct 120 ms 9532 KB Output is correct
7 Correct 120 ms 9496 KB Output is correct
8 Correct 129 ms 9544 KB Output is correct
9 Correct 121 ms 9544 KB Output is correct
10 Correct 128 ms 9544 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 9516 KB Output is correct
2 Correct 86 ms 9808 KB Output is correct
3 Correct 84 ms 9544 KB Output is correct
4 Correct 88 ms 9552 KB Output is correct
5 Correct 121 ms 9544 KB Output is correct
6 Correct 93 ms 9544 KB Output is correct
7 Correct 95 ms 9800 KB Output is correct
8 Correct 129 ms 9580 KB Output is correct
9 Correct 124 ms 9544 KB Output is correct
10 Correct 94 ms 9540 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 9548 KB Output is correct
2 Correct 122 ms 9484 KB Output is correct
3 Correct 123 ms 9716 KB Output is correct
4 Correct 128 ms 9544 KB Output is correct
5 Correct 129 ms 9544 KB Output is correct
6 Correct 120 ms 9532 KB Output is correct
7 Correct 120 ms 9496 KB Output is correct
8 Correct 129 ms 9544 KB Output is correct
9 Correct 121 ms 9544 KB Output is correct
10 Correct 128 ms 9544 KB Output is correct
11 Correct 82 ms 9516 KB Output is correct
12 Correct 86 ms 9808 KB Output is correct
13 Correct 84 ms 9544 KB Output is correct
14 Correct 88 ms 9552 KB Output is correct
15 Correct 121 ms 9544 KB Output is correct
16 Correct 93 ms 9544 KB Output is correct
17 Correct 95 ms 9800 KB Output is correct
18 Correct 129 ms 9580 KB Output is correct
19 Correct 124 ms 9544 KB Output is correct
20 Correct 94 ms 9540 KB Output is correct
21 Incorrect 126 ms 9540 KB Output isn't correct
22 Halted 0 ms 0 KB -