Submission #329203

#	Time	Username	Problem	Language	Result	Execution time	Memory
329203		Mahdi_Shokoufi	Feast (NOI19_feast)	C++17	71 / 100	50 ms	61164 KiB

feast

//In The Name of Allah
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())

const int N = 3e5 + 10;
const int M = 2010;
const ll mod = 1e9 + 7;
const int inf = 1e9 + 10;

ll a[N], dp[2][M][M];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, k, mn = inf, cn = 0, sum = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
        mn = min(mn, a[i]);
        cn += a[i] < 0;
        sum += a[i];
    }
    if (0 <= mn)
        return cout << sum, 0;
    if (cn == 1){
        ll pre = 0, suf = 0;
        for (int i = 1; i <= n && 0 <= a[i]; i ++)
            pre += a[i];
        for (int i = n; i >= 1 && 0 <= a[i]; i --)
            suf += a[i];
        if (2 <= k)
            return cout << sum - mn, 0;
        return cout << max({sum, pre, suf}), 0;
    }
    if (k == 1){
        ll ans = 0, cur = 0;
        for (int i = 1; i <= n; i ++){
            cur = max(0LL, cur + a[i]);
            ans = max(ans, cur);
        }
        return cout << ans, 0;
    }
    if (n <= 2000 && k <= 2000){
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= k; j ++){
                dp[0][i][j] = a[i] + max(dp[0][i - 1][j], dp[1][i - 1][j - 1]);
                dp[1][i][j] = max(dp[1][i - 1][j], dp[0][i][j]);
            }
        }
        return cout << dp[1][n][k], 0;
    }
    return 0;
}

• 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: 0 / 29