oj.uz

Submission #1025601

# Submission time Handle Problem Language Result Execution time Memory
1025601 2024-07-17T08:03:04 Z ach00 Feast (NOI19_feast) C++14
41 / 100
 177 ms 192548 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
vector<ll> W;
vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(2005, vector<ll>(2005, -1)));

ll solve(int i, int l, bool w) {
    if(dp[w][i][l] != -1) return dp[w][i][l];
    if(l > k || i >= n) return 0;
    ll ans = numeric_limits<int>::min();
    if(w == false) {
        ans = max(ans, solve(i+1, l , false));
        ans = max(ans, solve(i+1, l+1, true));
    } else {
        ans = max(ans, solve(i+1, l, true));
        ans = max(ans, solve(i+1, l, false));
    }
    ans += (w) ? W[i] : 0;
    dp[w][i][l] = ans;
    return ans;
}

int main() {
    cin >> n >> k;
    W.resize(n); for(auto &a : W) cin >> a;
    cout << max(solve(0, 0, false), solve(0, 1, true));
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 177 ms 192548 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 40 ms 94800 KB Output is correct
2 Correct 39 ms 94816 KB Output is correct
3 Correct 40 ms 94980 KB Output is correct
4 Correct 40 ms 94804 KB Output is correct
5 Correct 48 ms 94804 KB Output is correct
6 Correct 46 ms 94804 KB Output is correct
7 Correct 45 ms 94992 KB Output is correct
8 Correct 45 ms 94800 KB Output is correct
9 Correct 60 ms 94884 KB Output is correct
10 Correct 46 ms 94800 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94800 KB Output is correct
2 Correct 39 ms 94816 KB Output is correct
3 Correct 40 ms 94980 KB Output is correct
4 Correct 40 ms 94804 KB Output is correct
5 Correct 48 ms 94804 KB Output is correct
6 Correct 46 ms 94804 KB Output is correct
7 Correct 45 ms 94992 KB Output is correct
8 Correct 45 ms 94800 KB Output is correct
9 Correct 60 ms 94884 KB Output is correct
10 Correct 46 ms 94800 KB Output is correct
11 Correct 47 ms 94796 KB Output is correct
12 Correct 47 ms 94800 KB Output is correct
13 Correct 63 ms 94812 KB Output is correct
14 Correct 48 ms 94828 KB Output is correct
15 Correct 48 ms 94804 KB Output is correct
16 Correct 54 ms 94948 KB Output is correct
17 Correct 51 ms 94804 KB Output is correct
18 Correct 55 ms 94800 KB Output is correct
19 Correct 46 ms 94800 KB Output is correct
20 Correct 48 ms 94828 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94800 KB Output is correct
2 Correct 39 ms 94816 KB Output is correct
3 Correct 40 ms 94980 KB Output is correct
4 Correct 40 ms 94804 KB Output is correct
5 Correct 48 ms 94804 KB Output is correct
6 Correct 46 ms 94804 KB Output is correct
7 Correct 45 ms 94992 KB Output is correct
8 Correct 45 ms 94800 KB Output is correct
9 Correct 60 ms 94884 KB Output is correct
10 Correct 46 ms 94800 KB Output is correct
11 Correct 47 ms 94796 KB Output is correct
12 Correct 47 ms 94800 KB Output is correct
13 Correct 63 ms 94812 KB Output is correct
14 Correct 48 ms 94828 KB Output is correct
15 Correct 48 ms 94804 KB Output is correct
16 Correct 54 ms 94948 KB Output is correct
17 Correct 51 ms 94804 KB Output is correct
18 Correct 55 ms 94800 KB Output is correct
19 Correct 46 ms 94800 KB Output is correct
20 Correct 48 ms 94828 KB Output is correct
21 Correct 60 ms 95032 KB Output is correct
22 Correct 93 ms 95144 KB Output is correct
23 Correct 74 ms 95312 KB Output is correct
24 Correct 62 ms 95004 KB Output is correct
25 Correct 67 ms 95044 KB Output is correct
26 Correct 62 ms 95036 KB Output is correct
27 Correct 69 ms 95148 KB Output is correct
28 Correct 53 ms 95060 KB Output is correct
29 Correct 52 ms 95060 KB Output is correct
30 Correct 50 ms 95060 KB Output is correct

Subtask #7
0 / 29.0

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