oj.uz

Submission #1102958

# Submission time Handle Problem Language Result Execution time Memory
1102958 2024-10-19T09:21:50 Z alexdumitru Feast (NOI19_feast) C++14
12 / 100
 145 ms 9804 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 = 1;
    ll dr = 3e14;
    while (st <= dr) {
        ll mij = (st + dr) / 2;
        auto v = ok(mij);
        if (v.second == k) {
            ans = v.first + mij * k;
            return;
        } else if (v.second > k) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }
 
    auto v = ok(st);
 
    ans = v.first + st * v.second;
}
 
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 138 ms 9536 KB Output is correct
2 Correct 126 ms 9544 KB Output is correct
3 Correct 132 ms 9776 KB Output is correct
4 Correct 127 ms 9544 KB Output is correct
5 Correct 128 ms 9556 KB Output is correct
6 Correct 124 ms 9448 KB Output is correct
7 Correct 142 ms 9544 KB Output is correct
8 Correct 142 ms 9576 KB Output is correct
9 Correct 130 ms 9548 KB Output is correct
10 Correct 145 ms 9548 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9532 KB Output is correct
2 Correct 63 ms 9804 KB Output is correct
3 Correct 62 ms 9552 KB Output is correct
4 Correct 97 ms 9544 KB Output is correct
5 Correct 80 ms 9452 KB Output is correct
6 Correct 60 ms 9544 KB Output is correct
7 Correct 102 ms 9576 KB Output is correct
8 Correct 78 ms 9548 KB Output is correct
9 Correct 77 ms 9552 KB Output is correct
10 Correct 96 ms 9748 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 9536 KB Output is correct
2 Correct 126 ms 9544 KB Output is correct
3 Correct 132 ms 9776 KB Output is correct
4 Correct 127 ms 9544 KB Output is correct
5 Correct 128 ms 9556 KB Output is correct
6 Correct 124 ms 9448 KB Output is correct
7 Correct 142 ms 9544 KB Output is correct
8 Correct 142 ms 9576 KB Output is correct
9 Correct 130 ms 9548 KB Output is correct
10 Correct 145 ms 9548 KB Output is correct
11 Correct 72 ms 9532 KB Output is correct
12 Correct 63 ms 9804 KB Output is correct
13 Correct 62 ms 9552 KB Output is correct
14 Correct 97 ms 9544 KB Output is correct
15 Correct 80 ms 9452 KB Output is correct
16 Correct 60 ms 9544 KB Output is correct
17 Correct 102 ms 9576 KB Output is correct
18 Correct 78 ms 9548 KB Output is correct
19 Correct 77 ms 9552 KB Output is correct
20 Correct 96 ms 9748 KB Output is correct
21 Incorrect 105 ms 9544 KB Output isn't correct
22 Halted 0 ms 0 KB -