Submission #1025635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1025635	2024-07-17T08:20:54 Z	Zicrus	Feast (NOI19_feast)	C++17	59 / 100	174 ms	262144 KB

feast

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<vector<ll>> dp(n, vector<ll>(k+1));
    vector<vector<ll>> dpSeg(n, vector<ll>(k+1));
    for (int j = 1; j <= k; j++) {
        dpSeg[0][j] = max(0ll, a[0]);
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = max(dp[i-1][j], dpSeg[i-1][j]);
            dpSeg[i][j] = max(dp[i-1][j-1], dpSeg[i-1][j]) + a[i];
        }
    }

    cout << max(dp.back().back(), dpSeg.back().back());
}

Subtask #1

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	174 ms	262144 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	34644 KB	Output is correct
2	Correct	61 ms	35520 KB	Output is correct
3	Correct	68 ms	34640 KB	Output is correct
4	Runtime error	141 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	119 ms	35012 KB	Output is correct
2	Correct	111 ms	34640 KB	Output is correct
3	Correct	96 ms	35016 KB	Output is correct
4	Correct	100 ms	34716 KB	Output is correct
5	Correct	102 ms	35012 KB	Output is correct
6	Correct	98 ms	35260 KB	Output is correct
7	Correct	100 ms	35292 KB	Output is correct
8	Correct	104 ms	34996 KB	Output is correct
9	Correct	119 ms	35412 KB	Output is correct
10	Correct	98 ms	35408 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #5

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	604 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct

Subtask #6

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	604 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	4 ms	6492 KB	Output is correct
22	Correct	25 ms	51448 KB	Output is correct
23	Correct	7 ms	12124 KB	Output is correct
24	Correct	4 ms	7004 KB	Output is correct
25	Correct	5 ms	9564 KB	Output is correct
26	Correct	3 ms	5976 KB	Output is correct
27	Correct	5 ms	9052 KB	Output is correct
28	Correct	1 ms	1372 KB	Output is correct
29	Correct	1 ms	1372 KB	Output is correct
30	Correct	1 ms	604 KB	Output is correct

Subtask #7

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	174 ms	262144 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-