oj.uz

Submission #953721

# Submission time Handle Problem Language Result Execution time Memory
953721 2024-03-26T14:36:47 Z PM1 Boarding Passes (BOI22_passes) C++17
100 / 100
 494 ms 628492 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define ll long long
const int mxn=1e5+5,mxg=15;
int g,n,a[mxn],cnt=0,all[mxg+5];
string s;
ll dp[(1<<mxg)],res[(1<<mxg)][mxg+5],z=1,zz=2;
ll pre[mxn][mxg+5][mxg+5],suf[mxn][mxg+5][mxg+5],num[mxn];
vector<int>v[mxg+5];
ll cal(ll mask,int c,ll y){
	ll sum=0,x=v[c][y];
	for(int i=1;i<=cnt;i++){
		if(mask&(1<<(i-1))){
			sum+=pre[x+1][c][i]+suf[x+1][c][i];
		}
	}
	sum*=2;
	sum+=y*(y-1)/2;
	y=all[c]-y;
	sum+=y*(y-1)/2;
	return sum;
}
ll calu(ll mask,int c){
	ll sum=0;
	for(int i=1;i<=cnt;i++){
		if(mask&(1<<(i-1))){
			sum+=suf[0][c][i];
		}
	}
	sum*=2;
	ll y=all[c];
	sum+=y*(y-1)/2;
	return sum;
}
ll f(ll mask,ll c){
	ll res=calu(mask,c);
	int L=0,R=v[c].size()-1;
	while(L<R){
		int mid=(L+R)/2;
		ll x=cal(mask,c,mid);
		ll y=cal(mask,c,mid+1);
		if(x<=y)
			R=mid;
		else
			L=mid+1;
	}
	res=min(res,cal(mask,c,L));
	//cout<<mask<<" "<<c<<" "<<res<<'\n';
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	n=s.size();
	for(int i=1;i<=mxg;i++)
		v[i].push_back(-1);
	for(int i=0;i<n;i++){
		int x=s[i];
		a[x]=(a[x]==0)?++cnt:a[x];
		x=a[x];
		all[x]+=z;
		v[x].push_back(i);
	}
	for(int i=0;i<n;i++){
		int x=s[i];
		x=a[x];
		for(int j=1;j<=cnt;j++){
			for(int k=1;k<=cnt;k++){
				if(j==k)continue;
				pre[i+1][j][k]=pre[i][j][k];
				if(x==j)
					pre[i+1][j][k]+=num[k];
			}
		}
		num[x]++;
	}
	memset(num,0,sizeof num);
	for(int i=n-1;i>=0;i--){
		int x=s[i];
		x=a[x];
		for(int j=1;j<=cnt;j++){
			for(int k=1;k<=cnt;k++){
				if(j==k)continue;
				suf[i][j][k]=suf[i+1][j][k];
				if(x==j)
					suf[i][j][k]+=num[k];
			}
		}
		num[x]++;
	}
	for(int i=1;i<(1<<cnt);i++){
		dp[i]=1e18;
		for(int j=0;j<cnt;j++){
			if(i&(1<<j)){
				int y=i-(1<<j);
				dp[i]=min(dp[i],dp[y]+f(y,j+1));
			}
		}
	}
	cout<<dp[(1<<cnt)-1]/2;
	if(dp[(1<<cnt)-1]%2)
		cout<<".5";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 4856 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 5140 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 5396 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 5400 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 5400 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 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 4700 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 7004 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 7004 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 6828 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 4700 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 7004 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 4700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 4700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 4696 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 4700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 4700 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 4700 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 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 4700 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 7004 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 7004 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 6828 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 4700 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 7004 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 4700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 4700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 4696 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 4700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 4700 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 4700 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 4852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 7004 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 7004 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 7004 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 4700 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 7004 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 4700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 4696 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 4700 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 4700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 4656 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 4952 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 4700 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 4700 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 24 ms 67712 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 13 ms 67672 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 13 ms 67660 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 14 ms 67420 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 14 ms 64860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 12 ms 64860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 13 ms 64860 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 13 ms 64860 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 12 ms 64860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 13 ms 64860 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 4856 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 5140 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 5396 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 5400 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 5400 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 4700 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 7004 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 7004 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 2 ms 6828 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 4700 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 7004 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 4700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 4700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 4696 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 2 ms 4700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 4700 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 4700 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 4852 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 7004 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 7004 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 7004 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 4700 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 7004 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 4700 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 4700 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 4696 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 4700 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 4700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 4656 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 4952 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 4700 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 4700 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 24 ms 67712 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 13 ms 67672 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 13 ms 67660 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 14 ms 67420 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 14 ms 64860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 12 ms 64860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 13 ms 64860 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 13 ms 64860 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 12 ms 64860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 13 ms 64860 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 4696 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 83 ms 5028 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 4700 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 4564 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 4564 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 5400 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 5396 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 5400 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 5396 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 4700 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 4700 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 2 ms 7004 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 7004 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 6848 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 4700 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 7004 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 4700 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 4776 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 4696 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 4700 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 4700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 4700 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 4700 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 4700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 4700 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 4700 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 4700 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 4700 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 13 ms 67672 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 13 ms 67672 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 12 ms 67800 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 13 ms 67416 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 12 ms 64860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 12 ms 64860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 13 ms 65008 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 13 ms 64860 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 12 ms 64856 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 14 ms 64856 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 494 ms 628288 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 40 ms 5208 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 431 ms 628272 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 299 ms 628476 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 60 ms 4924 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 395 ms 628308 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 415 ms 628492 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 406 ms 626000 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 414 ms 625904 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 424 ms 626000 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 443 ms 625784 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 422 ms 626124 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 300 ms 624980 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 410 ms 625820 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'