# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
407040 | 2021-05-18T11:47:41 Z | mat_v | The short shank; Redemption (BOI21_prison) | C++14 | 33 ms | 1740 KB |
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i)) #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i)) #define mod 998244353 #define xx first #define yy second #define all(a) (a).begin(), (a).end() #define pb push_back #define ll long long #define pii pair<int,int> using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less) mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int n,d,t; int niz[100005]; int dp[505][505]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> d >> t; ff(i,1,n){ cin >> niz[i]; } d = min(n,d); fb(i,n,1){ ff(j,0,d){ if(j == 0){ int mn = niz[i]-1; ff(k,i,n){ mn++; mn = min(mn, niz[k]); if(mn <= t)dp[i][j]++; } continue; } int mn = niz[i] - 1; int tr = 0; dp[i][j] = 1e9; ff(k,i,n){ mn++; mn = min(mn, niz[k]); if(mn <= t)tr++; dp[i][j] = min(dp[i][j], dp[k + 1][j - 1] + tr); } } } cout << dp[1][d] << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 3 ms | 1100 KB | Output is correct |
3 | Correct | 5 ms | 1100 KB | Output is correct |
4 | Correct | 17 ms | 1228 KB | Output is correct |
5 | Correct | 32 ms | 1348 KB | Output is correct |
6 | Correct | 3 ms | 1228 KB | Output is correct |
7 | Correct | 13 ms | 1248 KB | Output is correct |
8 | Correct | 5 ms | 1228 KB | Output is correct |
9 | Correct | 7 ms | 1228 KB | Output is correct |
10 | Correct | 16 ms | 1184 KB | Output is correct |
11 | Correct | 29 ms | 1268 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Runtime error | 14 ms | 1484 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 3 ms | 1100 KB | Output is correct |
3 | Correct | 5 ms | 1100 KB | Output is correct |
4 | Correct | 17 ms | 1228 KB | Output is correct |
5 | Correct | 32 ms | 1348 KB | Output is correct |
6 | Correct | 3 ms | 1228 KB | Output is correct |
7 | Correct | 13 ms | 1248 KB | Output is correct |
8 | Correct | 5 ms | 1228 KB | Output is correct |
9 | Correct | 7 ms | 1228 KB | Output is correct |
10 | Correct | 16 ms | 1184 KB | Output is correct |
11 | Correct | 29 ms | 1268 KB | Output is correct |
12 | Correct | 1 ms | 332 KB | Output is correct |
13 | Correct | 4 ms | 1100 KB | Output is correct |
14 | Correct | 6 ms | 1092 KB | Output is correct |
15 | Correct | 20 ms | 1244 KB | Output is correct |
16 | Correct | 29 ms | 1184 KB | Output is correct |
17 | Correct | 4 ms | 1220 KB | Output is correct |
18 | Correct | 13 ms | 1272 KB | Output is correct |
19 | Correct | 5 ms | 1228 KB | Output is correct |
20 | Correct | 7 ms | 1228 KB | Output is correct |
21 | Correct | 18 ms | 1288 KB | Output is correct |
22 | Correct | 33 ms | 1188 KB | Output is correct |
23 | Runtime error | 2 ms | 460 KB | Execution killed with signal 11 |
24 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Runtime error | 11 ms | 1740 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 3 ms | 1100 KB | Output is correct |
3 | Correct | 5 ms | 1100 KB | Output is correct |
4 | Correct | 17 ms | 1228 KB | Output is correct |
5 | Correct | 32 ms | 1348 KB | Output is correct |
6 | Correct | 3 ms | 1228 KB | Output is correct |
7 | Correct | 13 ms | 1248 KB | Output is correct |
8 | Correct | 5 ms | 1228 KB | Output is correct |
9 | Correct | 7 ms | 1228 KB | Output is correct |
10 | Correct | 16 ms | 1184 KB | Output is correct |
11 | Correct | 29 ms | 1268 KB | Output is correct |
12 | Correct | 1 ms | 332 KB | Output is correct |
13 | Correct | 4 ms | 1100 KB | Output is correct |
14 | Correct | 6 ms | 1092 KB | Output is correct |
15 | Correct | 20 ms | 1244 KB | Output is correct |
16 | Correct | 29 ms | 1184 KB | Output is correct |
17 | Correct | 4 ms | 1220 KB | Output is correct |
18 | Correct | 13 ms | 1272 KB | Output is correct |
19 | Correct | 5 ms | 1228 KB | Output is correct |
20 | Correct | 7 ms | 1228 KB | Output is correct |
21 | Correct | 18 ms | 1288 KB | Output is correct |
22 | Correct | 33 ms | 1188 KB | Output is correct |
23 | Runtime error | 2 ms | 460 KB | Execution killed with signal 11 |
24 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 3 ms | 1100 KB | Output is correct |
3 | Correct | 5 ms | 1100 KB | Output is correct |
4 | Correct | 17 ms | 1228 KB | Output is correct |
5 | Correct | 32 ms | 1348 KB | Output is correct |
6 | Correct | 3 ms | 1228 KB | Output is correct |
7 | Correct | 13 ms | 1248 KB | Output is correct |
8 | Correct | 5 ms | 1228 KB | Output is correct |
9 | Correct | 7 ms | 1228 KB | Output is correct |
10 | Correct | 16 ms | 1184 KB | Output is correct |
11 | Correct | 29 ms | 1268 KB | Output is correct |
12 | Correct | 1 ms | 332 KB | Output is correct |
13 | Runtime error | 14 ms | 1484 KB | Execution killed with signal 11 |
14 | Halted | 0 ms | 0 KB | - |