# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
408872 | 2021-05-19T18:26:00 Z | mat_v | Group Photo (JOI21_ho_t3) | C++14 | 5000 ms | 452 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; int niz[5005]; int dp[5005]; int ans[5005]; int poz[5005]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; ff(i,1,n){ cin >> niz[i]; poz[niz[i]] = i; } dp[n] = 0; fb(i,n-1,0){ ans[0] = 0; dp[i] = 1e9; ff(j,i+1,n){ ans[j-i] = ans[j-i-1]; ff(r,1,poz[j] - 1){ if(niz[r] > i)ans[j-i]++; } ff(r,poz[j]+1,n){ if(niz[r] < j && niz[r] > i)ans[j-i]--; } dp[i] = min(dp[i], ans[j-i] + dp[j]); } } cout << dp[0] << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 324 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 324 KB | Output is correct |
11 | Correct | 1 ms | 332 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 1 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 1 ms | 332 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 320 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 324 KB | Output is correct |
11 | Correct | 1 ms | 332 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 1 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 1 ms | 332 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 320 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
21 | Correct | 11 ms | 332 KB | Output is correct |
22 | Correct | 12 ms | 332 KB | Output is correct |
23 | Correct | 9 ms | 332 KB | Output is correct |
24 | Correct | 12 ms | 340 KB | Output is correct |
25 | Correct | 12 ms | 344 KB | Output is correct |
26 | Correct | 12 ms | 340 KB | Output is correct |
27 | Correct | 9 ms | 332 KB | Output is correct |
28 | Correct | 9 ms | 332 KB | Output is correct |
29 | Correct | 10 ms | 332 KB | Output is correct |
30 | Correct | 9 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 324 KB | Output is correct |
11 | Correct | 1 ms | 332 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 1 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 1 ms | 332 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 320 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
21 | Correct | 11 ms | 332 KB | Output is correct |
22 | Correct | 12 ms | 332 KB | Output is correct |
23 | Correct | 9 ms | 332 KB | Output is correct |
24 | Correct | 12 ms | 340 KB | Output is correct |
25 | Correct | 12 ms | 344 KB | Output is correct |
26 | Correct | 12 ms | 340 KB | Output is correct |
27 | Correct | 9 ms | 332 KB | Output is correct |
28 | Correct | 9 ms | 332 KB | Output is correct |
29 | Correct | 10 ms | 332 KB | Output is correct |
30 | Correct | 9 ms | 340 KB | Output is correct |
31 | Correct | 541 ms | 332 KB | Output is correct |
32 | Correct | 539 ms | 340 KB | Output is correct |
33 | Correct | 545 ms | 332 KB | Output is correct |
34 | Correct | 545 ms | 332 KB | Output is correct |
35 | Correct | 539 ms | 332 KB | Output is correct |
36 | Correct | 546 ms | 332 KB | Output is correct |
37 | Correct | 541 ms | 332 KB | Output is correct |
38 | Correct | 553 ms | 332 KB | Output is correct |
39 | Correct | 540 ms | 332 KB | Output is correct |
40 | Correct | 534 ms | 452 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 324 KB | Output is correct |
11 | Correct | 1 ms | 332 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 1 ms | 332 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 1 ms | 332 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 320 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 1 ms | 332 KB | Output is correct |
21 | Correct | 11 ms | 332 KB | Output is correct |
22 | Correct | 12 ms | 332 KB | Output is correct |
23 | Correct | 9 ms | 332 KB | Output is correct |
24 | Correct | 12 ms | 340 KB | Output is correct |
25 | Correct | 12 ms | 344 KB | Output is correct |
26 | Correct | 12 ms | 340 KB | Output is correct |
27 | Correct | 9 ms | 332 KB | Output is correct |
28 | Correct | 9 ms | 332 KB | Output is correct |
29 | Correct | 10 ms | 332 KB | Output is correct |
30 | Correct | 9 ms | 340 KB | Output is correct |
31 | Correct | 541 ms | 332 KB | Output is correct |
32 | Correct | 539 ms | 340 KB | Output is correct |
33 | Correct | 545 ms | 332 KB | Output is correct |
34 | Correct | 545 ms | 332 KB | Output is correct |
35 | Correct | 539 ms | 332 KB | Output is correct |
36 | Correct | 546 ms | 332 KB | Output is correct |
37 | Correct | 541 ms | 332 KB | Output is correct |
38 | Correct | 553 ms | 332 KB | Output is correct |
39 | Correct | 540 ms | 332 KB | Output is correct |
40 | Correct | 534 ms | 452 KB | Output is correct |
41 | Execution timed out | 5071 ms | 384 KB | Time limit exceeded |
42 | Halted | 0 ms | 0 KB | - |