oj.uz

Submission #603249

# Submission time Handle Problem Language Result Execution time Memory
603249 2022-07-23T18:47:27 Z CSQ31 Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 13736 KB 
//consider scc graph
//u -> v
//if u bad then v must be bad
//so every ingoing edge into v must be good and sum of sub(tree?graph?) must be >= minimal parent
//i dont even need scc,only scc is if all values are equal okay yes
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
typedef long double ld;
const int MAXN = 1e5+5;
int g[MAXN];
ll dp[MAXN],pref[MAXN],suff[MAXN];
ll cost[15][15][MAXN];
vector<int>p[15];
int main()
{
	string s;
	cin>>s;
	int n = sz(s);
	int m = 0;
	for(int i=0;i<n;i++){
		g[i] = s[i] - 'A';
		m = max(g[i],m);
		p[g[i]].pb(i);
	}
	m++;
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(i==j)continue; //j go after i
			int s0 = sz(p[i]);
			int s1 = sz(p[j]);
			//last "l" at here
			int ptr = -1;
			ll a = 0,b = 0;
			for(int k=0;k<s1;k++){
				while(ptr+1<s0 && p[i][ptr+1] < p[j][k]){
					ptr++;
					a+=2;
				}
				b+=a;
				cost[i][j][k+1] = b;
			}
			a = b = 0;
			ptr = s0;
			for(int k=s1-1;k>=0;k--){
				while(ptr-1>=0 && p[i][ptr-1] > p[j][k]){
					ptr--;
					a+=2;
				}
				b+=a;
				cost[i][j][k]+= b;
			}
		}
	}
	for(int mask=0;mask<(1<<m);mask++)dp[mask] = 1e18;
	dp[0] = 0;
	for(int mask=0;mask<(1<<m);mask++){
		vector<int>v;
		for(int j=0;j<m;j++){
			if(mask&(1<<j))v.pb(j);
		}
		for(int j=0;j<m;j++){
			if(mask&(1<<j))continue;
			int s1 = sz(p[j]);
			for(int k=0;k<=s1;k++){
				ll c = 0;
				for(int x:v)c+=cost[x][j][k];
				c+=k * 1LL *(k-1)/2;
				c+=(s1-k) * 1LL *(s1-k-1)/2;
				dp[mask+(1<<j)] = min(dp[mask+(1<<j)],dp[mask]+c);
			}
		}
	}
	ld ans = dp[(1<<m)-1];
	ans/=2;
	cout<<fixed<<setprecision(5)<<ans<<'\n';
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 1360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 1472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 1472 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 1452 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 564 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 564 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 356 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 0 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 9 ms 1108 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 10 ms 1164 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 39 ms 1664 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 36 ms 1620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 38 ms 1708 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 35 ms 1648 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 36 ms 1620 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 38 ms 1656 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 40 ms 1660 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 47 ms 1664 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 38 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 38 ms 1620 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 1360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 1472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 1472 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 1452 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 564 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 356 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 0 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 0 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 9 ms 1108 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 10 ms 1164 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 39 ms 1664 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 36 ms 1620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 38 ms 1708 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 35 ms 1648 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 36 ms 1620 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 38 ms 1656 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 40 ms 1660 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 47 ms 1664 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 38 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 38 ms 1620 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 15 ms 1108 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 16 ms 1760 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 1320 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 1360 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 1324 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 1324 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 0 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 11 ms 1156 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 11 ms 1108 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 46 ms 1668 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 39 ms 1620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 36 ms 1620 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 35 ms 1620 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 36 ms 1620 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 38 ms 1644 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 36 ms 1620 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 35 ms 1620 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 37 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 40 ms 1620 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2091 ms 13736 KB Time limit exceeded
97 Halted 0 ms 0 KB -