oj.uz

Submission #953717

# Submission time Handle Problem Language Result Execution time Memory
953717 2024-03-26T14:32:20 Z PM1 Boarding Passes (BOI22_passes) C++17
55 / 100
 25 ms 67676 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=1e18;
	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
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 2 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 2 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 4700 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 5144 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 2 ms 5400 KB 1st numbers differ - expected: '1100977812.5000000000', found: '-1046505835.5000000000', error = '1.9505240011'
8 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 4700 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 7000 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 2 ms 7004 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 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 4696 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 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 4700 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 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 2 ms 7000 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 2 ms 7004 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 2 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 4696 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 3 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 4700 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 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 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 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 4696 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 4696 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 4700 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 4704 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 4648 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 4700 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 4700 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 25 ms 67676 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 12 ms 67676 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 10 ms 67668 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 13 ms 67416 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 13 ms 64860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 14 ms 64860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 12 ms 64824 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 12 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 12 ms 64860 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 2 ms 4700 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 2 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 4700 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 5144 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 2 ms 5400 KB 1st numbers differ - expected: '1100977812.5000000000', found: '-1046505835.5000000000', error = '1.9505240011'
8 Halted 0 ms 0 KB -