Submission #486386

# Submission time Handle Problem Language Result Execution time Memory
486386 2021-11-11T14:35:09 Z KienTran Feast (NOI19_feast) C++14
59 / 100
136 ms 262148 KB
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 3e5 + 5;

int n, k, a[O];
vector <vector <int>> f[2];

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    for (int i = 0; i < 2; ++ i){
        f[i].resize(n + 1);
        for (int j = 0; j <= n; ++ j) f[i][j].resize(k + 1);
    }

    for (int i = 1; i <= n; ++ i){
        for (int j = 1; j <= k; ++ j){
            f[0][i][j] = max(f[1][i - 1][j - 1], f[0][i - 1][j]) + a[i];
            f[1][i][j] = max({f[0][i][j], f[1][i - 1][j - 1], f[1][i - 1][j]});
        }
    }

    cout << f[1][n][k];
}

Compilation message

feast.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main(){
      | ^~~~
# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 56 ms 35732 KB Output is correct
2 Correct 59 ms 36532 KB Output is correct
3 Correct 54 ms 35648 KB Output is correct
4 Runtime error 123 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 68 ms 38032 KB Output is correct
2 Correct 67 ms 37628 KB Output is correct
3 Correct 69 ms 37964 KB Output is correct
4 Correct 70 ms 37592 KB Output is correct
5 Correct 70 ms 38028 KB Output is correct
6 Correct 73 ms 38328 KB Output is correct
7 Correct 70 ms 38368 KB Output is correct
8 Correct 70 ms 37984 KB Output is correct
9 Correct 69 ms 38424 KB Output is correct
10 Correct 70 ms 38340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 324 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 324 KB Output is correct
11 Correct 0 ms 448 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 324 KB Output is correct
11 Correct 0 ms 448 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 4 ms 6476 KB Output is correct
22 Correct 34 ms 51532 KB Output is correct
23 Correct 8 ms 12236 KB Output is correct
24 Correct 5 ms 6988 KB Output is correct
25 Correct 6 ms 9544 KB Output is correct
26 Correct 4 ms 5832 KB Output is correct
27 Correct 5 ms 9036 KB Output is correct
28 Correct 1 ms 1484 KB Output is correct
29 Correct 2 ms 1356 KB Output is correct
30 Correct 1 ms 588 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -