# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
823753 | 2023-08-13T04:48:23 Z | Amylopectin | Boarding Passes (BOI22_passes) | C++14 | 2000 ms | 50060 KB |
#include <stdio.h> #include <iostream> #include <vector> #include <string.h> #include <stdlib.h> using namespace std; const int mxn = 1e6 + 10; vector<int> ar[mxn] = {},cli[mxn] = {}; double avinv[mxn] = {},fst[mxn] = {},ami = -1; char s[mxn] = {},alp[mxn] = {}; int u[mxn] = {}; int re(int cn,int dep,int cru,double cva) { int i,j,cm,fn,fm,fru,fva; double cmi = 0; if(dep == cru) { if(ami == -1) { ami = cva; } else { ami = min(cva,ami); } return 0; } for(i=1; i<cru; i++) { if(u[i] == 1) { continue; } u[i] = 1; cli[dep].clear(); fru = 0; fva = 0; for(j=0; j<ar[i].size(); j++) { fn = ar[i][j]; while(fru < cli[dep-1].size() && cli[dep-1][fru] < fn) { cli[dep].push_back(cli[dep-1][fru]); fru ++; } cli[dep].push_back(fn); fva += fru; fst[j] = fva + avinv[j+1]; } while(fru < cli[dep-1].size()) { cli[dep].push_back(cli[dep-1][fru]); fru ++; } fru = cli[dep-1].size()-1; fva = 0; cmi = fst[ar[i].size()-1]; for(j=ar[i].size()-1; j>=0; j--) { fn = ar[i][j]; while(fru >= 0 && cli[dep-1][fru] > fn) { fru --; } fva += cli[dep-1].size() - fru - 1; if(j > 0) { cmi = min(cmi,fst[j-1] + fva + avinv[ar[i].size() - j]); } else { cmi = min(cmi, fva + avinv[ar[i].size() - j]); } } re(i,dep+1,cru,cva + cmi); u[i] = 0; } return 0; } int main() { int i,j,n,m,cn,cm,fn,fm,cru = 1; double p; scanf("%s",&s); n = strlen(s); for(i=2; i<=n; i++) { p = i; avinv[i] = p*(p-1) / 4; } for(i=0; i<n; i++) { cn = s[i] - 'A' + 1; if(alp[cn] == 0) { alp[cn] = cru; cru ++; } cm = alp[cn]; ar[cm].push_back(i); } re(-1,1,cru,0); printf("%.3lf\n",ami); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 47308 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 24 ms | 47200 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 27 ms | 47256 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 23 ms | 47188 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 24 ms | 47308 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 26 ms | 49612 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 27 ms | 50060 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 25 ms | 49936 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 31 ms | 49904 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 47280 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 24 ms | 47388 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 27 ms | 47288 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 28 ms | 47188 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 25 ms | 47268 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 23 ms | 47276 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 25 ms | 47276 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 23 ms | 47260 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 24 ms | 47280 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 28 ms | 47196 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 23 ms | 47224 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 24 ms | 47284 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 23 ms | 47224 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 24 ms | 47312 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 23 ms | 47268 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 24 ms | 47264 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 27 ms | 47400 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 47280 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 24 ms | 47388 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 27 ms | 47288 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 28 ms | 47188 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 25 ms | 47268 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 23 ms | 47276 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 25 ms | 47276 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 23 ms | 47260 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 24 ms | 47280 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 28 ms | 47196 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 23 ms | 47224 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 24 ms | 47284 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 23 ms | 47224 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 24 ms | 47312 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 23 ms | 47268 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 24 ms | 47264 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 27 ms | 47400 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
18 | Correct | 22 ms | 47188 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
19 | Correct | 22 ms | 47296 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
20 | Correct | 26 ms | 47260 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
21 | Correct | 26 ms | 47304 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
22 | Correct | 26 ms | 47188 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
23 | Correct | 22 ms | 47284 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
24 | Correct | 25 ms | 47300 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
25 | Correct | 24 ms | 47192 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
26 | Correct | 24 ms | 47188 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
27 | Correct | 25 ms | 47288 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
28 | Correct | 23 ms | 47192 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
29 | Correct | 25 ms | 47244 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
30 | Correct | 28 ms | 47188 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
31 | Correct | 23 ms | 47304 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
32 | Correct | 24 ms | 47308 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
33 | Correct | 24 ms | 47284 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
34 | Correct | 29 ms | 47272 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
35 | Correct | 26 ms | 47572 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
36 | Correct | 23 ms | 47536 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
37 | Execution timed out | 2069 ms | 47744 KB | Time limit exceeded |
38 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 47308 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 24 ms | 47200 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 27 ms | 47256 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 23 ms | 47188 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 24 ms | 47308 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 26 ms | 49612 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 27 ms | 50060 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 25 ms | 49936 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 31 ms | 49904 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 | Correct | 27 ms | 47280 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 | Correct | 24 ms | 47388 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 | Correct | 27 ms | 47288 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
13 | Correct | 28 ms | 47188 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
14 | Correct | 25 ms | 47268 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
15 | Correct | 23 ms | 47276 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
16 | Correct | 25 ms | 47276 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
17 | Correct | 23 ms | 47260 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
18 | Correct | 24 ms | 47280 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
19 | Correct | 28 ms | 47196 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
20 | Correct | 23 ms | 47224 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
21 | Correct | 24 ms | 47284 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
22 | Correct | 23 ms | 47224 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
23 | Correct | 24 ms | 47312 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
24 | Correct | 23 ms | 47268 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
25 | Correct | 24 ms | 47264 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
26 | Correct | 27 ms | 47400 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
27 | Correct | 22 ms | 47188 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
28 | Correct | 22 ms | 47296 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
29 | Correct | 26 ms | 47260 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
30 | Correct | 26 ms | 47304 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
31 | Correct | 26 ms | 47188 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
32 | Correct | 22 ms | 47284 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
33 | Correct | 25 ms | 47300 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
34 | Correct | 24 ms | 47192 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
35 | Correct | 24 ms | 47188 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
36 | Correct | 25 ms | 47288 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
37 | Correct | 23 ms | 47192 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
38 | Correct | 25 ms | 47244 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
39 | Correct | 28 ms | 47188 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
40 | Correct | 23 ms | 47304 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
41 | Correct | 24 ms | 47308 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
42 | Correct | 24 ms | 47284 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
43 | Correct | 29 ms | 47272 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
44 | Correct | 26 ms | 47572 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
45 | Correct | 23 ms | 47536 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
46 | Execution timed out | 2069 ms | 47744 KB | Time limit exceeded |
47 | Halted | 0 ms | 0 KB | - |