oj.uz

Submission #1101064

# Submission time Handle Problem Language Result Execution time Memory
1101064 2024-10-15T12:54:10 Z trie Feast (NOI19_feast) C++17
41 / 100
 14 ms 63312 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 = 805;
const int MOD = 1e9 + 7;

int n, k;
ll pr[N], dp[N][N], mx[N][N];

void solve() {
    cin >> n >> k;
    for(int x, i = 1 ; i <= n ; i++) {
        cin >> x;
        pr[i] = pr[i - 1] + x;
    }

    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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 14416 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3064 KB Output is correct
2 Correct 1 ms 2896 KB Output is correct
3 Correct 2 ms 2896 KB Output is correct
4 Correct 1 ms 2896 KB Output is correct
5 Correct 2 ms 2896 KB Output is correct
6 Correct 1 ms 2896 KB Output is correct
7 Correct 1 ms 2896 KB Output is correct
8 Correct 1 ms 2896 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2896 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3064 KB Output is correct
2 Correct 1 ms 2896 KB Output is correct
3 Correct 2 ms 2896 KB Output is correct
4 Correct 1 ms 2896 KB Output is correct
5 Correct 2 ms 2896 KB Output is correct
6 Correct 1 ms 2896 KB Output is correct
7 Correct 1 ms 2896 KB Output is correct
8 Correct 1 ms 2896 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2896 KB Output is correct
11 Correct 2 ms 11344 KB Output is correct
12 Correct 2 ms 9296 KB Output is correct
13 Correct 2 ms 9516 KB Output is correct
14 Correct 2 ms 11516 KB Output is correct
15 Correct 2 ms 9296 KB Output is correct
16 Correct 2 ms 9296 KB Output is correct
17 Correct 2 ms 11344 KB Output is correct
18 Correct 2 ms 9296 KB Output is correct
19 Correct 2 ms 9296 KB Output is correct
20 Correct 2 ms 11220 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3064 KB Output is correct
2 Correct 1 ms 2896 KB Output is correct
3 Correct 2 ms 2896 KB Output is correct
4 Correct 1 ms 2896 KB Output is correct
5 Correct 2 ms 2896 KB Output is correct
6 Correct 1 ms 2896 KB Output is correct
7 Correct 1 ms 2896 KB Output is correct
8 Correct 1 ms 2896 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2896 KB Output is correct
11 Correct 2 ms 11344 KB Output is correct
12 Correct 2 ms 9296 KB Output is correct
13 Correct 2 ms 9516 KB Output is correct
14 Correct 2 ms 11516 KB Output is correct
15 Correct 2 ms 9296 KB Output is correct
16 Correct 2 ms 9296 KB Output is correct
17 Correct 2 ms 11344 KB Output is correct
18 Correct 2 ms 9296 KB Output is correct
19 Correct 2 ms 9296 KB Output is correct
20 Correct 2 ms 11220 KB Output is correct
21 Correct 11 ms 61776 KB Output is correct
22 Correct 13 ms 61520 KB Output is correct
23 Correct 11 ms 61776 KB Output is correct
24 Correct 11 ms 61768 KB Output is correct
25 Correct 11 ms 63312 KB Output is correct
26 Correct 14 ms 63056 KB Output is correct
27 Correct 11 ms 63196 KB Output is correct
28 Correct 11 ms 63056 KB Output is correct
29 Correct 12 ms 62168 KB Output is correct
30 Correct 11 ms 61792 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 14416 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -