Submission #1140446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140446		Pekiban	Feast (NOI19_feast)	C++20	100 / 100	761 ms	10024 KiB

feast

#include <bits/stdc++.h>

using namespace std;
using ld = long double;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int a[n+1]; ll S[n+1]; S[0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        S[i] = S[i-1] + a[i];
    }
    ld l = 0, r = 1e15;
    ll ans = 0;
    for (int _ = 0; _ < 200; ++_) {
        ld m = (l + r)/2;
        ld dp[n+1]; int c[n+1];
        dp[0] = c[0] = 0;
        int p = 0;
        for (int i = 1; i <= n; ++i) {
            if (dp[p] - S[p] + S[i] - m >= dp[i-1]) 
                dp[i] = dp[p] - S[p] + S[i] - m, c[i] = c[p] + 1;
            else
                dp[i] = dp[i-1], c[i] = c[i-1];
            if (dp[i] - S[i] >= dp[p] - S[p])   p = i;
        }
        if (c[n] <= k)
            ans = roundl(dp[n] + c[n] * m), r = m;
        else
            l = m;
    }
    cout << ans << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29