Submission #832793

#	Time	Username	Problem	Language	Result	Execution time	Memory
832793		BamshooT	Feast (NOI19_feast)	C++14	41 / 100	1059 ms	31688 KiB

feast

#include <iostream>
#include <algorithm>
#include <cstring>
 
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ll long long
#define inf 1e18
 
using namespace std;
 
struct dt{
    ll t, c;
    bool operator < (const dt &x) const{
        return (t > x.t);
    }
};
 
const int N = 3e5 + 9;
int n, k, t, p;
ll dp[2009][2009], a[N], pre[N], res, cur;
 
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  //  freopen("nhap.inp", "r", stdin);
  //  freopen("xuat.out", "w", stdout);
    cin >> n >> k;
    FOR(i, 1, n) {
        cin >> a[i];
        t += (a[i] < 0);
        if (a[i] < 0) p = i;
        pre[i] = pre[i-1] + a[i];
        res = max(res, pre[i] - cur);
        cur = min(cur, pre[i]);
    }
    FOR(i, 1, k) {
        ll cur = 0;
        FOR(j, 1, n) {
            cur = max(cur, dp[i-1][j] - pre[j]);
            dp[i][j] = max(dp[i][j-1], pre[j] + cur);
        }
    }
    cout <<dp[k][n];
    return 0;
}

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