oj.uz

Submission #603258

# Submission time Handle Problem Language Result Execution time Memory
603258 2022-07-23T18:57:49 Z CSQ31 Boarding Passes (BOI22_passes) C++17
100 / 100
 190 ms 13860 KB 
#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];
ll comp(vector<int>&v,int j,int k){
	int s1 = sz(p[j]);
	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;
	return c;
	
}
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 l = 0,r = sz(p[j]);
			while(r-l>3){
				int m1 = l+(r-l)/3;
				int m2 = r-(r-l)/3;
				ll a = comp(v,j,m1);
				ll b = comp(v,j,m2);
				if(a == b){
					l = m1;
					r = m2;
				}
				if(a > b)l = m1;
				if(b > a)r = m2;				
			}
			for(int k=l;k<=r;k++){
				dp[mask+(1<<j)] = min(dp[mask+(1<<j)] , dp[mask] + comp(v,j,k));
			}
		}
	}
	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 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 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 3 ms 1360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 1360 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 1360 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 1360 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 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 468 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 1 ms 480 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 0 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 1 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 1 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 0 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 0 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 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 468 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 1 ms 480 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 0 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 1 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 1 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 0 ms 340 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 0 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 0 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 0 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 1 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 1 ms 1108 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 2 ms 1108 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 5 ms 1688 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 3 ms 1620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 3 ms 1748 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 2 ms 1620 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 4 ms 1620 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 4 ms 1620 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 4 ms 1620 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 4 ms 1620 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 4 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 4 ms 1620 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 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 3 ms 1360 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 1360 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 1360 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 1360 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 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 0 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 0 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 468 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 1 ms 480 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 0 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 1 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 1 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 0 ms 340 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 0 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 0 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 0 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 1 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 1 ms 1108 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 2 ms 1108 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 5 ms 1688 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 3 ms 1620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 3 ms 1748 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 2 ms 1620 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 4 ms 1620 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 4 ms 1620 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 4 ms 1620 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 4 ms 1620 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 4 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 4 ms 1620 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 17 ms 1192 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 24 ms 1764 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 340 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 1 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 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 3 ms 1232 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 1360 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 1360 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 4 ms 1360 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 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 0 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 0 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 1 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 0 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 1108 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 1108 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 5 ms 1620 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 3 ms 1620 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 3 ms 1620 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 3 ms 1620 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 3 ms 1620 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 3 ms 1620 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 4 ms 1620 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 4 ms 1620 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 4 ms 1620 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 4 ms 1620 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 190 ms 13792 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 13 ms 1500 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 150 ms 13652 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 39 ms 13652 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 19 ms 1748 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 74 ms 13692 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 189 ms 13720 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 163 ms 13780 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 161 ms 13780 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 184 ms 13776 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 162 ms 13796 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 168 ms 13792 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 91 ms 12644 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 169 ms 13860 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'