| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 129844 |
2019-07-13T10:35:10 Z |
RockyB |
Candies (JOI18_candies) |
C++17 |
|
94 ms |
32120 KB |
#include <bits/stdc++.h>
#define f first
#define s second
#define sz(x) (int)x.size()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define nl '\n'
#define ioi exit(0);
using namespace std;
typedef long long ll;
const int N = (int)2000 + 7;
const ll linf = (ll)1e18 + 7;
int n;
int a[N];
ll dp[N][N];
ll calc(int v, int cnt) {
if (cnt < 0) return -linf;
if (v < 1) {
if (!cnt) return 0;
return -linf;
}
if (~dp[v][cnt]) return dp[v][cnt];
return dp[v][cnt] = max(calc(v - 1, cnt), calc(v - 2, cnt - 1) + a[v]);
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef IOI
freopen ("in.txt", "r", stdin);
//freopen ("res.txt", "w", stdout);
#endif
cin >> n;
rep(i, 1, n) {
cin >> a[i];
}
memset(dp, -1, sizeof(dp));
rep(i, 1, (n + 1) / 2) {
cout << calc(n, i) << nl;
}
ioi
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 2 |
Correct |
79 ms |
32052 KB |
Output is correct |
| 3 |
Correct |
78 ms |
31992 KB |
Output is correct |
| 4 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 5 |
Correct |
94 ms |
32120 KB |
Output is correct |
| 6 |
Correct |
89 ms |
31992 KB |
Output is correct |
| 7 |
Correct |
77 ms |
31996 KB |
Output is correct |
| 8 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 9 |
Correct |
80 ms |
31992 KB |
Output is correct |
| 10 |
Correct |
78 ms |
31992 KB |
Output is correct |
| 11 |
Correct |
79 ms |
31992 KB |
Output is correct |
| 12 |
Correct |
84 ms |
31992 KB |
Output is correct |
| 13 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 14 |
Correct |
77 ms |
31992 KB |
Output is correct |
| 15 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 16 |
Correct |
77 ms |
31992 KB |
Output is correct |
| 17 |
Correct |
78 ms |
32120 KB |
Output is correct |
| 18 |
Correct |
79 ms |
31992 KB |
Output is correct |
| 19 |
Correct |
77 ms |
31992 KB |
Output is correct |
| 20 |
Correct |
75 ms |
31992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 2 |
Correct |
79 ms |
32052 KB |
Output is correct |
| 3 |
Correct |
78 ms |
31992 KB |
Output is correct |
| 4 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 5 |
Correct |
94 ms |
32120 KB |
Output is correct |
| 6 |
Correct |
89 ms |
31992 KB |
Output is correct |
| 7 |
Correct |
77 ms |
31996 KB |
Output is correct |
| 8 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 9 |
Correct |
80 ms |
31992 KB |
Output is correct |
| 10 |
Correct |
78 ms |
31992 KB |
Output is correct |
| 11 |
Correct |
79 ms |
31992 KB |
Output is correct |
| 12 |
Correct |
84 ms |
31992 KB |
Output is correct |
| 13 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 14 |
Correct |
77 ms |
31992 KB |
Output is correct |
| 15 |
Correct |
76 ms |
31992 KB |
Output is correct |
| 16 |
Correct |
77 ms |
31992 KB |
Output is correct |
| 17 |
Correct |
78 ms |
32120 KB |
Output is correct |
| 18 |
Correct |
79 ms |
31992 KB |
Output is correct |
| 19 |
Correct |
77 ms |
31992 KB |
Output is correct |
| 20 |
Correct |
75 ms |
31992 KB |
Output is correct |
| 21 |
Runtime error |
5 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 22 |
Halted |
0 ms |
0 KB |
- |
