oj.uz

Submission #652283

# Submission time Handle Problem Language Result Execution time Memory
652283 2022-10-22T02:08:21 Z inksamurai Boarding Passes (BOI22_passes) C++17
100 / 100
 1539 ms 354832 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3CZAtRo ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

const int inf=1e10;

void chmin(int&a,const int&b){
	a=min(a,b);
}

signed main(){
_3CZAtRo;
	int n;
	vi a;
	{
		string s;
		cin>>s;
		n=sz(s);
		vi tmp;
		rep(i,n){
			tmp.pb(s[i]-'A');
		}
		sort(tmp.begin(),tmp.end());
		tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
		rep(i,n){
			int v=lower_bound(tmp.begin(),tmp.end(),s[i]-'A')-tmp.begin();
			a.pb(v);
		}
	}
	
	const int si=sz(set<int>(a.begin(),a.end()));
	vec(vi) rbts(si);
	rep(i,n){
		rbts[a[i]].pb(i);
	}

	vec(vec(vi)) pf(si,vec(vi)(si,vi(n))),sf;
	sf=pf;
	rep(s,si){
		rep(t,si){
			if(s==t) continue;
			int cnt=0;
			rep(i,n){
				if(i) pf[s][t][i]=pf[s][t][i-1];
				if(a[i]==t){
					pf[s][t][i]+=cnt;
				}else if(a[i]==s){
					cnt+=1;
				}
			}
			cnt=0;
			per(i,n){
				if(i<n-1) sf[s][t][i]=sf[s][t][i+1];
				if(a[i]==t){
					sf[s][t][i]+=cnt;
				}else if(a[i]==s){
					cnt+=1;
				}
			}
		}
	}
	
	auto af1=[&](int v,int msk,int id)->int{
		int pos=(id==-1?id:rbts[v][id]);
		int res=0;
		rep(u,si){
			if(msk>>u&1){
				if(pos!=-1) res+=pf[u][v][pos];
				if(pos+1<n) res+=sf[u][v][pos+1];
			}
		}
		res=2*res;
		if(id!=-1){
			res+=((id+1)*id)/2+(sz(rbts[v])-id-1)*(sz(rbts[v])-id-2)/2;
		}else{
			res+=(sz(rbts[v])*(sz(rbts[v])-1))/2;
		}
		return res;
	};

	auto af0=[&](int v,int msk){
		int sj=sz(rbts[v]);
		int l=0,r=sj-1;
		while(r-l>3){
			int ml=(2*l+r)/3;
			int mr=(l+2*r)/3;
			int fl=af1(v,msk,ml);
			int fr=af1(v,msk,mr);
			if(fl<fr) r=mr;
			else l=ml;
		}
		int res=af1(v,msk,-1);
		rng(i,l,r+1){
			res=min(res,af1(v,msk,i));
		}
		return res;
	};

	vi dp(1<<si,inf);
	dp[0]=0;
	rep(msk,1<<si){
		int now=dp[msk];
		rep(v,si){
			if(!(msk>>v&1)){
				int nmsk=msk|(1<<v);
				int wit=af0(v,msk);
				chmin(dp[nmsk],wit+now);
			}
		}
	}

	int ans=dp[(1<<si)-1];
	cout<<ans/2<<(ans%2?".5":"")<<"\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 ms 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 6 ms 4324 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 6 ms 4540 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 9 ms 4532 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 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 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 316 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 320 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 624 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 624 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 23 ms 16248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 22 ms 16172 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 18 ms 16112 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 26 ms 16116 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 24 ms 15896 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 26 ms 15860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 24 ms 15876 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 24 ms 15860 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 22 ms 15860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 22 ms 15860 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 340 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 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 5 ms 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 6 ms 4324 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 6 ms 4540 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 9 ms 4532 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 340 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 340 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 316 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 320 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 340 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 624 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 624 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 23 ms 16248 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 22 ms 16172 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 18 ms 16112 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 26 ms 16116 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 24 ms 15896 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 26 ms 15860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 24 ms 15876 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 24 ms 15860 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 22 ms 15860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 22 ms 15860 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 212 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 38 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 256 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 6 ms 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 6 ms 4332 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 7 ms 4540 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 7 ms 4540 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 340 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 324 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 340 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 340 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 340 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 736 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 624 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 23 ms 16112 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 24 ms 16112 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 19 ms 16240 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 23 ms 16092 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 23 ms 15852 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 25 ms 15796 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 30 ms 15884 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 26 ms 15860 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 27 ms 15896 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 29 ms 15860 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1539 ms 354812 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 24 ms 596 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 987 ms 354636 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 421 ms 354648 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 35 ms 596 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 1118 ms 354652 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 1238 ms 354832 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 1208 ms 353432 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 1212 ms 353404 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 1269 ms 353380 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 1232 ms 353396 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 1171 ms 353360 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 706 ms 307692 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 1275 ms 353472 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'