oj.uz

Submission #1101091

# Submission time Handle Problem Language Result Execution time Memory
1101091 2024-10-15T13:20:35 Z trie Feast (NOI19_feast) C++17
63 / 100
 97 ms 63072 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<ii, int>
#define ll long long
#define pb push_back
#define pli pair<ll, int>
#define all(v) (v).begin(), (v).end()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define cntbit(mask) __builtin_popcount(mask)
#define getbit(x, i) ((x >> i) & 1)
#define MASK(i) (1 << i)
#define pli pair<ll, int>
using namespace std;

template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;}

template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;}

const int N = 2005;
const int V = 3e5 + 5;
const int MOD = 1e9 + 7;

int n, k;
ll pr[V], dp[N][N], mx[N][N], a[V];
int negative, idx;

void solve() {
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        pr[i] = pr[i - 1] + a[i];
        if (a[i] < 0) {
            negative++;
            idx = i;
        }
    }

    if (!negative) return cout << pr[n], void();
    if (k == 1) { // kadane algorithm.
        ll sum = 0, mxsum = 0;
        for(int i = 1 ; i <= n ; i++) {
            sum += a[i];
            maximize(mxsum, sum);
            if (sum < 0) sum = 0;
        }
        return cout << mxsum, void();
    }
    //if (negative == 1) return cout << pr[n] - a[idx], void();

    for(int i = 1 ; i <= n ; i++) mx[i][0] = max(mx[i - 1][0], - pr[i]);

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++) {
            dp[i][j] = dp[i - 1][j];
            maximize(dp[i][j], mx[i][j - 1] + pr[i]);
            mx[i][j] = max(mx[i - 1][j], dp[i][j] - pr[i]);
        }

    cout << dp[n][k];
}

int main(void) {
    //freopen("task.inp", "r", stdin);
    //freopen("task.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    int t = 1; while(t--) solve();
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7736 KB Output is correct
2 Correct 30 ms 6736 KB Output is correct
3 Correct 23 ms 7924 KB Output is correct
4 Correct 29 ms 4956 KB Output is correct
5 Correct 25 ms 6728 KB Output is correct
6 Correct 21 ms 4956 KB Output is correct
7 Correct 22 ms 6472 KB Output is correct
8 Correct 23 ms 6984 KB Output is correct
9 Correct 21 ms 6480 KB Output is correct
10 Correct 25 ms 4936 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8056 KB Output is correct
2 Correct 21 ms 8016 KB Output is correct
3 Correct 15 ms 8016 KB Output is correct
4 Runtime error 97 ms 46804 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5640 KB Output is correct
2 Correct 27 ms 8020 KB Output is correct
3 Correct 27 ms 8024 KB Output is correct
4 Correct 28 ms 7832 KB Output is correct
5 Correct 28 ms 8032 KB Output is correct
6 Correct 28 ms 8004 KB Output is correct
7 Correct 26 ms 8028 KB Output is correct
8 Correct 28 ms 8020 KB Output is correct
9 Correct 26 ms 8028 KB Output is correct
10 Correct 26 ms 8068 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1104 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 1 ms 1104 KB Output is correct
7 Correct 2 ms 1276 KB Output is correct
8 Correct 1 ms 1104 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 1104 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1104 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 1 ms 1104 KB Output is correct
7 Correct 2 ms 1276 KB Output is correct
8 Correct 1 ms 1104 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 1104 KB Output is correct
11 Correct 4 ms 5200 KB Output is correct
12 Correct 2 ms 4688 KB Output is correct
13 Correct 3 ms 3664 KB Output is correct
14 Correct 3 ms 3664 KB Output is correct
15 Correct 3 ms 3664 KB Output is correct
16 Correct 2 ms 3408 KB Output is correct
17 Correct 3 ms 3920 KB Output is correct
18 Correct 3 ms 3664 KB Output is correct
19 Correct 3 ms 3664 KB Output is correct
20 Correct 3 ms 4176 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1104 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 1 ms 1104 KB Output is correct
7 Correct 2 ms 1276 KB Output is correct
8 Correct 1 ms 1104 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 1104 KB Output is correct
11 Correct 4 ms 5200 KB Output is correct
12 Correct 2 ms 4688 KB Output is correct
13 Correct 3 ms 3664 KB Output is correct
14 Correct 3 ms 3664 KB Output is correct
15 Correct 3 ms 3664 KB Output is correct
16 Correct 2 ms 3408 KB Output is correct
17 Correct 3 ms 3920 KB Output is correct
18 Correct 3 ms 3664 KB Output is correct
19 Correct 3 ms 3664 KB Output is correct
20 Correct 3 ms 4176 KB Output is correct
21 Correct 38 ms 61408 KB Output is correct
22 Correct 45 ms 60924 KB Output is correct
23 Correct 41 ms 61440 KB Output is correct
24 Correct 46 ms 61504 KB Output is correct
25 Correct 40 ms 63072 KB Output is correct
26 Correct 42 ms 62796 KB Output is correct
27 Correct 42 ms 63060 KB Output is correct
28 Correct 42 ms 62792 KB Output is correct
29 Correct 42 ms 62192 KB Output is correct
30 Correct 41 ms 61220 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7736 KB Output is correct
2 Correct 30 ms 6736 KB Output is correct
3 Correct 23 ms 7924 KB Output is correct
4 Correct 29 ms 4956 KB Output is correct
5 Correct 25 ms 6728 KB Output is correct
6 Correct 21 ms 4956 KB Output is correct
7 Correct 22 ms 6472 KB Output is correct
8 Correct 23 ms 6984 KB Output is correct
9 Correct 21 ms 6480 KB Output is correct
10 Correct 25 ms 4936 KB Output is correct
11 Correct 15 ms 8056 KB Output is correct
12 Correct 21 ms 8016 KB Output is correct
13 Correct 15 ms 8016 KB Output is correct
14 Runtime error 97 ms 46804 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -