Submission #1102958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102958		alexdumitru	Feast (NOI19_feast)	C++14	12 / 100	145 ms	9804 KiB

feast

#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 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29