# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
622520 |
2022-08-04T10:54:10 Z |
dozer |
Tortoise (CEOI21_tortoise) |
C++14 |
|
3000 ms |
392652 KB |
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pii pair<int, int>
#define st first
#define nd second
#define N 10005
#define modulo 1000000007
int dp[N][N];
vector<int> pg;
int arr[N], n;
int f(int time, int ind)
{
if (time > 2 * (n - 1) || ind > n) return 0;
if (arr[ind] == -1) return dp[time][ind] = f(time + 1, ind + 1);
if (dp[time][ind] != -1) return dp[time][ind];
auto it = lower_bound(pg.begin(), pg.end(), ind);
int nxt = modulo, prv = - modulo;
if (it != pg.end()) nxt = *it;
if (it != pg.begin())
{
it--;
prv = *it;
}
int dist = min(ind - prv, nxt - ind);
int tmp = time, inc = 0, ans = 0;
while(tmp <= ind * 2 - 2 && inc < arr[ind])
{
if (nxt <= n)
{
for (int i = ind + 1; i <= nxt; i++)//for the last candy we buy, we can go to the next pg and come back to a forward shop
{
ans = max(ans, f(tmp + nxt - ind + nxt - i, i) + inc + 1);
}
}
ans = max(ans, f(tmp + 1, ind + 1) + inc); // we can just continue to the next place without buying more candies
ans = max(ans, inc + 1);//buy it and finish the process
tmp += 2 * dist;
inc++;
}
ans = max(ans, f(tmp + 1, ind + 1) + inc);
ans = max(ans, f(time + 1, ind + 1));
//cout<<time<<sp<<ind<<sp<<ans<<endl;
return dp[time][ind] = ans;
}
int32_t main()
{
fastio();
memset(dp, -1, sizeof(dp));
cin>>n;
long long sum = 0;
for (int i = 1; i <= n; i++)
{
cin>>arr[i];
if (arr[i] == -1) pg.pb(i);
else sum += arr[i];
}
cout<<sum - f(0, 1)<<endl;
cerr<<"time taken: "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
392056 KB |
Output is correct |
2 |
Correct |
141 ms |
392080 KB |
Output is correct |
3 |
Correct |
137 ms |
392020 KB |
Output is correct |
4 |
Correct |
138 ms |
392036 KB |
Output is correct |
5 |
Correct |
139 ms |
391992 KB |
Output is correct |
6 |
Correct |
136 ms |
392044 KB |
Output is correct |
7 |
Correct |
138 ms |
392120 KB |
Output is correct |
8 |
Correct |
145 ms |
391964 KB |
Output is correct |
9 |
Correct |
141 ms |
392076 KB |
Output is correct |
10 |
Correct |
139 ms |
392044 KB |
Output is correct |
11 |
Correct |
138 ms |
392028 KB |
Output is correct |
12 |
Correct |
147 ms |
392004 KB |
Output is correct |
13 |
Correct |
140 ms |
392176 KB |
Output is correct |
14 |
Correct |
136 ms |
392008 KB |
Output is correct |
15 |
Correct |
143 ms |
392176 KB |
Output is correct |
16 |
Correct |
143 ms |
392076 KB |
Output is correct |
17 |
Correct |
139 ms |
392008 KB |
Output is correct |
18 |
Correct |
138 ms |
392020 KB |
Output is correct |
19 |
Correct |
138 ms |
392036 KB |
Output is correct |
20 |
Correct |
157 ms |
392012 KB |
Output is correct |
21 |
Correct |
140 ms |
391992 KB |
Output is correct |
22 |
Correct |
143 ms |
392016 KB |
Output is correct |
23 |
Correct |
144 ms |
392088 KB |
Output is correct |
24 |
Correct |
140 ms |
391996 KB |
Output is correct |
25 |
Correct |
141 ms |
391984 KB |
Output is correct |
26 |
Correct |
148 ms |
392064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
392056 KB |
Output is correct |
2 |
Correct |
141 ms |
392080 KB |
Output is correct |
3 |
Correct |
137 ms |
392020 KB |
Output is correct |
4 |
Correct |
138 ms |
392036 KB |
Output is correct |
5 |
Correct |
139 ms |
391992 KB |
Output is correct |
6 |
Correct |
136 ms |
392044 KB |
Output is correct |
7 |
Correct |
138 ms |
392120 KB |
Output is correct |
8 |
Correct |
145 ms |
391964 KB |
Output is correct |
9 |
Correct |
141 ms |
392076 KB |
Output is correct |
10 |
Correct |
139 ms |
392044 KB |
Output is correct |
11 |
Correct |
138 ms |
392028 KB |
Output is correct |
12 |
Correct |
147 ms |
392004 KB |
Output is correct |
13 |
Correct |
140 ms |
392176 KB |
Output is correct |
14 |
Correct |
136 ms |
392008 KB |
Output is correct |
15 |
Correct |
143 ms |
392176 KB |
Output is correct |
16 |
Correct |
143 ms |
392076 KB |
Output is correct |
17 |
Correct |
139 ms |
392008 KB |
Output is correct |
18 |
Correct |
138 ms |
392020 KB |
Output is correct |
19 |
Correct |
138 ms |
392036 KB |
Output is correct |
20 |
Correct |
157 ms |
392012 KB |
Output is correct |
21 |
Correct |
140 ms |
391992 KB |
Output is correct |
22 |
Correct |
143 ms |
392016 KB |
Output is correct |
23 |
Correct |
144 ms |
392088 KB |
Output is correct |
24 |
Correct |
140 ms |
391996 KB |
Output is correct |
25 |
Correct |
141 ms |
391984 KB |
Output is correct |
26 |
Correct |
148 ms |
392064 KB |
Output is correct |
27 |
Correct |
139 ms |
391980 KB |
Output is correct |
28 |
Correct |
141 ms |
392000 KB |
Output is correct |
29 |
Correct |
152 ms |
392060 KB |
Output is correct |
30 |
Correct |
143 ms |
392004 KB |
Output is correct |
31 |
Correct |
142 ms |
392016 KB |
Output is correct |
32 |
Correct |
138 ms |
392092 KB |
Output is correct |
33 |
Correct |
148 ms |
392012 KB |
Output is correct |
34 |
Correct |
153 ms |
392012 KB |
Output is correct |
35 |
Correct |
141 ms |
392012 KB |
Output is correct |
36 |
Correct |
142 ms |
392028 KB |
Output is correct |
37 |
Correct |
171 ms |
391992 KB |
Output is correct |
38 |
Correct |
143 ms |
391988 KB |
Output is correct |
39 |
Correct |
141 ms |
391988 KB |
Output is correct |
40 |
Correct |
144 ms |
392104 KB |
Output is correct |
41 |
Correct |
149 ms |
392060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
392056 KB |
Output is correct |
2 |
Correct |
141 ms |
392080 KB |
Output is correct |
3 |
Correct |
137 ms |
392020 KB |
Output is correct |
4 |
Correct |
138 ms |
392036 KB |
Output is correct |
5 |
Correct |
139 ms |
391992 KB |
Output is correct |
6 |
Correct |
136 ms |
392044 KB |
Output is correct |
7 |
Correct |
138 ms |
392120 KB |
Output is correct |
8 |
Correct |
145 ms |
391964 KB |
Output is correct |
9 |
Correct |
141 ms |
392076 KB |
Output is correct |
10 |
Correct |
139 ms |
392044 KB |
Output is correct |
11 |
Correct |
138 ms |
392028 KB |
Output is correct |
12 |
Correct |
147 ms |
392004 KB |
Output is correct |
13 |
Correct |
140 ms |
392176 KB |
Output is correct |
14 |
Correct |
136 ms |
392008 KB |
Output is correct |
15 |
Correct |
143 ms |
392176 KB |
Output is correct |
16 |
Correct |
143 ms |
392076 KB |
Output is correct |
17 |
Correct |
139 ms |
392008 KB |
Output is correct |
18 |
Correct |
138 ms |
392020 KB |
Output is correct |
19 |
Correct |
138 ms |
392036 KB |
Output is correct |
20 |
Correct |
157 ms |
392012 KB |
Output is correct |
21 |
Correct |
140 ms |
391992 KB |
Output is correct |
22 |
Correct |
143 ms |
392016 KB |
Output is correct |
23 |
Correct |
144 ms |
392088 KB |
Output is correct |
24 |
Correct |
140 ms |
391996 KB |
Output is correct |
25 |
Correct |
141 ms |
391984 KB |
Output is correct |
26 |
Correct |
148 ms |
392064 KB |
Output is correct |
27 |
Correct |
139 ms |
391980 KB |
Output is correct |
28 |
Correct |
141 ms |
392000 KB |
Output is correct |
29 |
Correct |
152 ms |
392060 KB |
Output is correct |
30 |
Correct |
143 ms |
392004 KB |
Output is correct |
31 |
Correct |
142 ms |
392016 KB |
Output is correct |
32 |
Correct |
138 ms |
392092 KB |
Output is correct |
33 |
Correct |
148 ms |
392012 KB |
Output is correct |
34 |
Correct |
153 ms |
392012 KB |
Output is correct |
35 |
Correct |
141 ms |
392012 KB |
Output is correct |
36 |
Correct |
142 ms |
392028 KB |
Output is correct |
37 |
Correct |
171 ms |
391992 KB |
Output is correct |
38 |
Correct |
143 ms |
391988 KB |
Output is correct |
39 |
Correct |
141 ms |
391988 KB |
Output is correct |
40 |
Correct |
144 ms |
392104 KB |
Output is correct |
41 |
Correct |
149 ms |
392060 KB |
Output is correct |
42 |
Correct |
147 ms |
392056 KB |
Output is correct |
43 |
Correct |
145 ms |
392020 KB |
Output is correct |
44 |
Correct |
140 ms |
392012 KB |
Output is correct |
45 |
Correct |
159 ms |
392040 KB |
Output is correct |
46 |
Correct |
140 ms |
391988 KB |
Output is correct |
47 |
Correct |
141 ms |
392092 KB |
Output is correct |
48 |
Correct |
140 ms |
392024 KB |
Output is correct |
49 |
Correct |
153 ms |
392012 KB |
Output is correct |
50 |
Correct |
143 ms |
392136 KB |
Output is correct |
51 |
Correct |
146 ms |
391988 KB |
Output is correct |
52 |
Correct |
150 ms |
392072 KB |
Output is correct |
53 |
Correct |
153 ms |
391984 KB |
Output is correct |
54 |
Correct |
153 ms |
392012 KB |
Output is correct |
55 |
Correct |
166 ms |
392044 KB |
Output is correct |
56 |
Correct |
142 ms |
392076 KB |
Output is correct |
57 |
Correct |
142 ms |
392048 KB |
Output is correct |
58 |
Correct |
143 ms |
392100 KB |
Output is correct |
59 |
Correct |
154 ms |
392076 KB |
Output is correct |
60 |
Correct |
159 ms |
392044 KB |
Output is correct |
61 |
Correct |
139 ms |
392020 KB |
Output is correct |
62 |
Correct |
144 ms |
392112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
392056 KB |
Output is correct |
2 |
Correct |
141 ms |
392080 KB |
Output is correct |
3 |
Correct |
137 ms |
392020 KB |
Output is correct |
4 |
Correct |
138 ms |
392036 KB |
Output is correct |
5 |
Correct |
139 ms |
391992 KB |
Output is correct |
6 |
Correct |
136 ms |
392044 KB |
Output is correct |
7 |
Correct |
138 ms |
392120 KB |
Output is correct |
8 |
Correct |
145 ms |
391964 KB |
Output is correct |
9 |
Correct |
141 ms |
392076 KB |
Output is correct |
10 |
Correct |
139 ms |
392044 KB |
Output is correct |
11 |
Correct |
138 ms |
392028 KB |
Output is correct |
12 |
Correct |
147 ms |
392004 KB |
Output is correct |
13 |
Correct |
140 ms |
392176 KB |
Output is correct |
14 |
Correct |
136 ms |
392008 KB |
Output is correct |
15 |
Correct |
143 ms |
392176 KB |
Output is correct |
16 |
Correct |
143 ms |
392076 KB |
Output is correct |
17 |
Correct |
139 ms |
392008 KB |
Output is correct |
18 |
Correct |
138 ms |
392020 KB |
Output is correct |
19 |
Correct |
138 ms |
392036 KB |
Output is correct |
20 |
Correct |
157 ms |
392012 KB |
Output is correct |
21 |
Correct |
140 ms |
391992 KB |
Output is correct |
22 |
Correct |
143 ms |
392016 KB |
Output is correct |
23 |
Correct |
144 ms |
392088 KB |
Output is correct |
24 |
Correct |
140 ms |
391996 KB |
Output is correct |
25 |
Correct |
141 ms |
391984 KB |
Output is correct |
26 |
Correct |
148 ms |
392064 KB |
Output is correct |
27 |
Correct |
139 ms |
391980 KB |
Output is correct |
28 |
Correct |
141 ms |
392000 KB |
Output is correct |
29 |
Correct |
152 ms |
392060 KB |
Output is correct |
30 |
Correct |
143 ms |
392004 KB |
Output is correct |
31 |
Correct |
142 ms |
392016 KB |
Output is correct |
32 |
Correct |
138 ms |
392092 KB |
Output is correct |
33 |
Correct |
148 ms |
392012 KB |
Output is correct |
34 |
Correct |
153 ms |
392012 KB |
Output is correct |
35 |
Correct |
141 ms |
392012 KB |
Output is correct |
36 |
Correct |
142 ms |
392028 KB |
Output is correct |
37 |
Correct |
171 ms |
391992 KB |
Output is correct |
38 |
Correct |
143 ms |
391988 KB |
Output is correct |
39 |
Correct |
141 ms |
391988 KB |
Output is correct |
40 |
Correct |
144 ms |
392104 KB |
Output is correct |
41 |
Correct |
149 ms |
392060 KB |
Output is correct |
42 |
Correct |
147 ms |
392056 KB |
Output is correct |
43 |
Correct |
145 ms |
392020 KB |
Output is correct |
44 |
Correct |
140 ms |
392012 KB |
Output is correct |
45 |
Correct |
159 ms |
392040 KB |
Output is correct |
46 |
Correct |
140 ms |
391988 KB |
Output is correct |
47 |
Correct |
141 ms |
392092 KB |
Output is correct |
48 |
Correct |
140 ms |
392024 KB |
Output is correct |
49 |
Correct |
153 ms |
392012 KB |
Output is correct |
50 |
Correct |
143 ms |
392136 KB |
Output is correct |
51 |
Correct |
146 ms |
391988 KB |
Output is correct |
52 |
Correct |
150 ms |
392072 KB |
Output is correct |
53 |
Correct |
153 ms |
391984 KB |
Output is correct |
54 |
Correct |
153 ms |
392012 KB |
Output is correct |
55 |
Correct |
166 ms |
392044 KB |
Output is correct |
56 |
Correct |
142 ms |
392076 KB |
Output is correct |
57 |
Correct |
142 ms |
392048 KB |
Output is correct |
58 |
Correct |
143 ms |
392100 KB |
Output is correct |
59 |
Correct |
154 ms |
392076 KB |
Output is correct |
60 |
Correct |
159 ms |
392044 KB |
Output is correct |
61 |
Correct |
139 ms |
392020 KB |
Output is correct |
62 |
Correct |
144 ms |
392112 KB |
Output is correct |
63 |
Correct |
493 ms |
392476 KB |
Output is correct |
64 |
Correct |
1336 ms |
392652 KB |
Output is correct |
65 |
Correct |
609 ms |
392588 KB |
Output is correct |
66 |
Correct |
703 ms |
392584 KB |
Output is correct |
67 |
Correct |
1037 ms |
392584 KB |
Output is correct |
68 |
Correct |
626 ms |
392584 KB |
Output is correct |
69 |
Correct |
707 ms |
392592 KB |
Output is correct |
70 |
Correct |
936 ms |
392632 KB |
Output is correct |
71 |
Execution timed out |
3077 ms |
392508 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
392056 KB |
Output is correct |
2 |
Correct |
141 ms |
392080 KB |
Output is correct |
3 |
Correct |
137 ms |
392020 KB |
Output is correct |
4 |
Correct |
138 ms |
392036 KB |
Output is correct |
5 |
Correct |
139 ms |
391992 KB |
Output is correct |
6 |
Correct |
136 ms |
392044 KB |
Output is correct |
7 |
Correct |
138 ms |
392120 KB |
Output is correct |
8 |
Correct |
145 ms |
391964 KB |
Output is correct |
9 |
Correct |
141 ms |
392076 KB |
Output is correct |
10 |
Correct |
139 ms |
392044 KB |
Output is correct |
11 |
Correct |
138 ms |
392028 KB |
Output is correct |
12 |
Correct |
147 ms |
392004 KB |
Output is correct |
13 |
Correct |
140 ms |
392176 KB |
Output is correct |
14 |
Correct |
136 ms |
392008 KB |
Output is correct |
15 |
Correct |
143 ms |
392176 KB |
Output is correct |
16 |
Correct |
143 ms |
392076 KB |
Output is correct |
17 |
Correct |
139 ms |
392008 KB |
Output is correct |
18 |
Correct |
138 ms |
392020 KB |
Output is correct |
19 |
Correct |
138 ms |
392036 KB |
Output is correct |
20 |
Correct |
157 ms |
392012 KB |
Output is correct |
21 |
Correct |
140 ms |
391992 KB |
Output is correct |
22 |
Correct |
143 ms |
392016 KB |
Output is correct |
23 |
Correct |
144 ms |
392088 KB |
Output is correct |
24 |
Correct |
140 ms |
391996 KB |
Output is correct |
25 |
Correct |
141 ms |
391984 KB |
Output is correct |
26 |
Correct |
148 ms |
392064 KB |
Output is correct |
27 |
Correct |
139 ms |
391980 KB |
Output is correct |
28 |
Correct |
141 ms |
392000 KB |
Output is correct |
29 |
Correct |
152 ms |
392060 KB |
Output is correct |
30 |
Correct |
143 ms |
392004 KB |
Output is correct |
31 |
Correct |
142 ms |
392016 KB |
Output is correct |
32 |
Correct |
138 ms |
392092 KB |
Output is correct |
33 |
Correct |
148 ms |
392012 KB |
Output is correct |
34 |
Correct |
153 ms |
392012 KB |
Output is correct |
35 |
Correct |
141 ms |
392012 KB |
Output is correct |
36 |
Correct |
142 ms |
392028 KB |
Output is correct |
37 |
Correct |
171 ms |
391992 KB |
Output is correct |
38 |
Correct |
143 ms |
391988 KB |
Output is correct |
39 |
Correct |
141 ms |
391988 KB |
Output is correct |
40 |
Correct |
144 ms |
392104 KB |
Output is correct |
41 |
Correct |
149 ms |
392060 KB |
Output is correct |
42 |
Correct |
147 ms |
392056 KB |
Output is correct |
43 |
Correct |
145 ms |
392020 KB |
Output is correct |
44 |
Correct |
140 ms |
392012 KB |
Output is correct |
45 |
Correct |
159 ms |
392040 KB |
Output is correct |
46 |
Correct |
140 ms |
391988 KB |
Output is correct |
47 |
Correct |
141 ms |
392092 KB |
Output is correct |
48 |
Correct |
140 ms |
392024 KB |
Output is correct |
49 |
Correct |
153 ms |
392012 KB |
Output is correct |
50 |
Correct |
143 ms |
392136 KB |
Output is correct |
51 |
Correct |
146 ms |
391988 KB |
Output is correct |
52 |
Correct |
150 ms |
392072 KB |
Output is correct |
53 |
Correct |
153 ms |
391984 KB |
Output is correct |
54 |
Correct |
153 ms |
392012 KB |
Output is correct |
55 |
Correct |
166 ms |
392044 KB |
Output is correct |
56 |
Correct |
142 ms |
392076 KB |
Output is correct |
57 |
Correct |
142 ms |
392048 KB |
Output is correct |
58 |
Correct |
143 ms |
392100 KB |
Output is correct |
59 |
Correct |
154 ms |
392076 KB |
Output is correct |
60 |
Correct |
159 ms |
392044 KB |
Output is correct |
61 |
Correct |
139 ms |
392020 KB |
Output is correct |
62 |
Correct |
144 ms |
392112 KB |
Output is correct |
63 |
Correct |
493 ms |
392476 KB |
Output is correct |
64 |
Correct |
1336 ms |
392652 KB |
Output is correct |
65 |
Correct |
609 ms |
392588 KB |
Output is correct |
66 |
Correct |
703 ms |
392584 KB |
Output is correct |
67 |
Correct |
1037 ms |
392584 KB |
Output is correct |
68 |
Correct |
626 ms |
392584 KB |
Output is correct |
69 |
Correct |
707 ms |
392592 KB |
Output is correct |
70 |
Correct |
936 ms |
392632 KB |
Output is correct |
71 |
Execution timed out |
3077 ms |
392508 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |