oj.uz

Submission #950580

# Submission time Handle Problem Language Result Execution time Memory
950580 2024-03-20T12:49:39 Z VMaksimoski008 Feast (NOI19_feast) C++14
22 / 100
 99 ms 5208 KB 
#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

int32_t main() {
    int n, K, neg = 0;
    cin >> n >> K;

    vector<int> v(n+1);
    vector<ll> pref(n+1);
    for(int i=1; i<=n; i++) {
        cin >> v[i];
        neg += (v[i] < 0);
        pref[i] = pref[i-1] + v[i];
    }

    if(neg == 0) {
        cout << pref[n] << '\n';
        return 0;
    }

    if(neg == 1) {
        ll N = 0;
        for(int &x : v) if(x < 0) N = x;
        
        if(K == n) {
            cout << pref[n] << '\n';
        } else if(K == 1) {
            ll ans1=0, ans2=0;
            for(int i=1; i<=n; i++) {
                if(v[i] < 0) break;
                ans1 += v[i];
            }
            for(int i=n; i>=1; i--) {
                if(v[i] < 0) break;
                ans2 += v[i];
            }
            cout << max(ans1, ans2);
        } else {
            cout << pref[n] - N;
        }

        return 0;
    }

    if(K == 1) {
        ll ans = 0, sum = 0, mn = 0;

        for(int i=1; i<=n; i++) {
            sum += v[i];
            ans = max(ans, sum - mn);
            mn = min(mn, sum);
        }

        cout << ans << '\n';
        return 0;
    }

    ll dp[n+1][K+1];
    memset(dp, 0, sizeof(dp));

    for(int i=1; i<=n; i++) {
        for(int j=0; j<=K; j++) {
            dp[i][j] = dp[i-1][j];
            if(j) {
                for(int k=1; k<i; k++) {
                    dp[i][j] = max(dp[i][j], dp[k-1][j-1] + pref[i] - pref[k-1]);
                }
            }
        }
    }

    cout << dp[n][K] << '\n';
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4972 KB Output is correct
2 Correct 82 ms 5060 KB Output is correct
3 Correct 82 ms 5116 KB Output is correct
4 Correct 81 ms 4952 KB Output is correct
5 Correct 83 ms 5052 KB Output is correct
6 Correct 83 ms 4980 KB Output is correct
7 Correct 79 ms 4956 KB Output is correct
8 Correct 99 ms 5068 KB Output is correct
9 Correct 80 ms 4952 KB Output is correct
10 Correct 81 ms 5036 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4952 KB Output is correct
2 Incorrect 45 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 4956 KB Output is correct
2 Correct 85 ms 4952 KB Output is correct
3 Correct 86 ms 4952 KB Output is correct
4 Correct 86 ms 4956 KB Output is correct
5 Correct 87 ms 5060 KB Output is correct
6 Correct 87 ms 4952 KB Output is correct
7 Correct 95 ms 5096 KB Output is correct
8 Correct 86 ms 4956 KB Output is correct
9 Correct 88 ms 4956 KB Output is correct
10 Correct 87 ms 5208 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4972 KB Output is correct
2 Correct 82 ms 5060 KB Output is correct
3 Correct 82 ms 5116 KB Output is correct
4 Correct 81 ms 4952 KB Output is correct
5 Correct 83 ms 5052 KB Output is correct
6 Correct 83 ms 4980 KB Output is correct
7 Correct 79 ms 4956 KB Output is correct
8 Correct 99 ms 5068 KB Output is correct
9 Correct 80 ms 4952 KB Output is correct
10 Correct 81 ms 5036 KB Output is correct
11 Correct 46 ms 4952 KB Output is correct
12 Incorrect 45 ms 4956 KB Output isn't correct
13 Halted 0 ms 0 KB -