Submission #892800

#	Time	Username	Problem	Language	Result	Execution time	Memory
892800		votranngocvy	Feast (NOI19_feast)	C++14	100 / 100	306 ms	36052 KiB

feast

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
const int N = 3e5 + 5;
const int inf = (long long)(1e9 * N);
int a[N],pre[N],n,k;

namespace sub1 {
    bool check_condition() {
        for (int i = 1; i <= n; i++)
            if (a[i] < 0) return false;
        return true;
    }
    void solve() {
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += a[i];
        cout << ans << "\n";
    }
}

namespace sub2 {
    bool check_condition() {
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            if (a[i] < 0) cnt++;
        return (cnt == 1);
    }
    void solve() {
        pre[0] = 0;
        int pos = 0;
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + a[i];
            if (a[i] < 0) pos = i;
        }
        if (k == 1) cout << max(max(pre[pos - 1],pre[n] - pre[pos]),pre[n]) << "\n";
        else cout << pre[n] - a[pos] << "\n";
    }
}

namespace sub3 {
    void solve() {
        int ans = -inf,sum = 0;
        for (int i = 1; i <= n; i++) {
            sum = max(sum + a[i],a[i]);
            ans = max(ans,sum);
        }
        cout << ans << "\n";
    }
}

namespace sub5 {
    int dp[305][305];
    void solve() {
        pre[0] = 0;
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int z = 1; z <= i; z++)
                    dp[i][j] = max(dp[i][j],dp[z - 1][j - 1] + pre[i] - pre[z - 1]);
            }
        cout << dp[n][k] << "\n";
    }
}

namespace sub7 {
    pair<ld,int>dp[N][3];
    bool check(ld val) {
        dp[0][0] = mp(0,0),dp[0][1] = mp(-inf,0);
        for (int i = 1; i <= n; i++) {
            dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]);
            dp[i][1] = max(mp(dp[i - 1][0].fi + (ld)a[i] - val,dp[i - 1][0].se + 1),mp(dp[i - 1][1].fi + (ld)a[i],dp[i - 1][1].se));
        }
        return (max(dp[n][0],dp[n][1]).se >= k);
    }
    void alien_trick() {
        ld l = 0,r = inf;
        while (l + 1e-3 < r) {
            ld mid = (l + r) / 2.0;
            if (check(mid)) l = mid + 1;
            else r = mid;
        }
        check(l);
        cout << (int)(k * l + max(dp[n][0],dp[n][1]).fi) << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    /*if (sub1::check_condition()) sub1::solve();
    else if (sub2::check_condition()) sub2::solve();
    else if (k == 1) sub3::solve();
    else if (n <= 300) sub5::solve();
    else */
    sub7::alien_trick();
}

• 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