oj.uz

Submission #950562

# Submission time Handle Problem Language Result Execution time Memory
950562 2024-03-20T12:38:04 Z VMaksimoski008 Feast (NOI19_feast) C++14
22 / 100
 264 ms 262144 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(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 82 ms 3920 KB Output is correct
2 Correct 105 ms 3908 KB Output is correct
3 Correct 83 ms 3932 KB Output is correct
4 Correct 82 ms 3928 KB Output is correct
5 Correct 80 ms 3896 KB Output is correct
6 Correct 101 ms 3676 KB Output is correct
7 Correct 81 ms 3676 KB Output is correct
8 Correct 80 ms 3676 KB Output is correct
9 Correct 80 ms 3672 KB Output is correct
10 Correct 80 ms 3884 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3856 KB Output is correct
2 Correct 46 ms 3932 KB Output is correct
3 Correct 43 ms 3676 KB Output is correct
4 Runtime error 264 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3908 KB Output is correct
2 Correct 86 ms 3672 KB Output is correct
3 Correct 86 ms 3672 KB Output is correct
4 Correct 91 ms 3676 KB Output is correct
5 Correct 87 ms 3676 KB Output is correct
6 Correct 87 ms 3928 KB Output is correct
7 Correct 87 ms 3932 KB Output is correct
8 Correct 87 ms 3900 KB Output is correct
9 Correct 90 ms 3936 KB Output is correct
10 Correct 99 ms 3932 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 348 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 348 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 82 ms 3920 KB Output is correct
2 Correct 105 ms 3908 KB Output is correct
3 Correct 83 ms 3932 KB Output is correct
4 Correct 82 ms 3928 KB Output is correct
5 Correct 80 ms 3896 KB Output is correct
6 Correct 101 ms 3676 KB Output is correct
7 Correct 81 ms 3676 KB Output is correct
8 Correct 80 ms 3676 KB Output is correct
9 Correct 80 ms 3672 KB Output is correct
10 Correct 80 ms 3884 KB Output is correct
11 Correct 44 ms 3856 KB Output is correct
12 Correct 46 ms 3932 KB Output is correct
13 Correct 43 ms 3676 KB Output is correct
14 Runtime error 264 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -