oj.uz

Submission #652272

# Submission time Handle Problem Language Result Execution time Memory
652272 2022-10-22T01:01:19 Z inksamurai Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 5168 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...);}

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);
		}
	}
	// rep(i,n){
	// 	cout<<a[i]<<" ";
	// }
	// print();
	int si=sz(set<int>(a.begin(),a.end()));
	vec(vi) rbts(si);
	rep(i,n){
		rbts[a[i]].pb(i);
	}
	const int inf=1e15;
	vi dp(1<<si,inf);
	dp[0]=0;
	rep(msk,1<<si){
		vi usd(n);
		rep(v,si){
			if(msk>>v&1){
				for(auto j:rbts[v]){
					usd[j]=1;
				}
			}
		}
		int now=dp[msk];
		rep(v,si){
			if(!(msk>>v&1)){
				int nmsk=msk|(1<<v);
				for(auto j:rbts[v]){
					usd[j]=2;
				}
				int w=inf;
				{
					vi pf(n);
					int cnt1=0,cnt2=0;
					rep(i,n){
						if(i){
							pf[i]+=pf[i-1];
						}
						if(usd[i]==2){
							pf[i]+=cnt2;
							pf[i]+=cnt1*2;
							cnt2+=1;
						}else if(usd[i]==1){
							cnt1+=1;
						}
					}
					vi sf(n);
					cnt1=0,cnt2=0;
					per(i,n){
						if(i<n-1){
							sf[i]+=sf[i+1];
						}
						if(usd[i]==2){
							sf[i]+=cnt2;
							sf[i]+=cnt1*2;
							cnt2+=1;
						}else if(usd[i]==1){
							cnt1+=1;
						}
					}
					w=min(sf[0],pf[n-1]);
					rep(i,n-1){
						w=min(w,pf[i]+sf[i+1]);
					}
					// if(msk==0 and v==1){
					// 	rep(i,n){
					// 		cout<<pf[i]<<" ";
					// 	}	
					// 	print();
					// }
				}
				chmin(dp[nmsk],w+now);
				for(auto j:rbts[v]){
					usd[j]=0;
				}
			}
		}
	}
	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 6 ms 3804 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 7 ms 4292 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 8 ms 4540 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 8 ms 4540 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 320 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 312 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 212 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 212 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 320 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 316 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 320 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 320 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 312 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 212 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 212 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 320 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 316 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 320 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 240 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 320 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 324 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 212 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 462 ms 948 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 480 ms 828 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 459 ms 748 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 462 ms 820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 439 ms 888 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 449 ms 856 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 460 ms 900 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 445 ms 780 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 461 ms 796 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 458 ms 868 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 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 6 ms 3804 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 7 ms 4292 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 8 ms 4540 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 8 ms 4540 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 320 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 312 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 212 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 212 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 320 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 316 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 320 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 240 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 316 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 320 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 320 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 324 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 212 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 462 ms 948 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 480 ms 828 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 459 ms 748 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 462 ms 820 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 439 ms 888 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 449 ms 856 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 460 ms 900 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 445 ms 780 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 461 ms 796 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 458 ms 868 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 59 ms 468 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 316 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 324 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 7 ms 3776 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 7 ms 4376 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 8 ms 4540 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 8 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 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 324 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 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 328 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 324 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 320 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 324 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 316 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 624 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 468 ms 940 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 469 ms 748 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 467 ms 744 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 469 ms 1240 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 452 ms 916 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 450 ms 824 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 453 ms 836 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 444 ms 788 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 451 ms 792 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 449 ms 800 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2073 ms 5168 KB Time limit exceeded
97 Halted 0 ms 0 KB -