oj.uz

Submission #953714

# Submission time Handle Problem Language Result Execution time Memory
953714 2024-03-26T14:30:08 Z PM1 Boarding Passes (BOI22_passes) C++17
55 / 100
 18 ms 67752 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,int 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 f(ll mask,ll c){
	ll res=cal(mask,c,0);
	int L=1,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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 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 4696 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 4952 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 5400 KB 1st numbers differ - expected: '772893586.0000000000', found: '472065006.5000000000', error = '0.3892238012'
7 Halted 0 ms 0 KB -

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 4564 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 1 ms 7004 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 4696 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 4952 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 1 ms 4700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 4696 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 4836 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 4564 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 1 ms 7004 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 4696 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 4952 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 1 ms 4700 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 4696 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 4836 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 4700 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 1 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 4780 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 4820 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 4700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 4696 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 4696 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 4956 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 4696 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 18 ms 67752 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 14 ms 67672 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 10 ms 67676 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 12 ms 67596 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 12 ms 64856 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 12 ms 65036 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 12 ms 64860 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 12 ms 65176 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 12 ms 64856 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 12 ms 64868 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 4696 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 4696 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 4952 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Incorrect 2 ms 5400 KB 1st numbers differ - expected: '772893586.0000000000', found: '472065006.5000000000', error = '0.3892238012'
7 Halted 0 ms 0 KB -