oj.uz

답안 #652282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652282 2022-10-22T02:06:58 Z inksamurai Boarding Passes (BOI22_passes) C++17
100 / 100
 1358 ms 354808 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);
		}
	}

	// rep(i,n){
	// 	cout<<a[i]<<" ";
	// }
	// print();

	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);
				// print(msk,v,wit);
				chmin(dp[nmsk],wit+now);
			}
		}
	}

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 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 0 ms 212 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 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 7 ms 4204 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 6 ms 4388 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 4412 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 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 0 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 212 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 0 ms 212 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 0 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 340 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 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 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 660 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 28 ms 16112 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 24 ms 16160 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 19 ms 16112 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 21 ms 16104 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 21 ms 15860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 22 ms 15860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 22 ms 15860 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 23 ms 15860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 21 ms 15860 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 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 0 ms 212 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 3812 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 7 ms 4204 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 6 ms 4388 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 6 ms 4412 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 0 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 0 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 212 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 0 ms 212 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 0 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 340 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 340 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 0 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 660 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 28 ms 16112 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 24 ms 16160 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 19 ms 16112 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 21 ms 16104 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 21 ms 15860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 22 ms 15860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 22 ms 15860 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 23 ms 15860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 21 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 40 ms 596 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 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 0 ms 288 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 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 4256 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 6 ms 4412 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 7 ms 4412 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 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 0 ms 340 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 340 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 340 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 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 23 ms 16112 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 22 ms 16112 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 20 ms 16112 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 24 ms 15988 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 24 ms 15860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 21 ms 15860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 23 ms 15944 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 23 ms 15884 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 21 ms 15860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 21 ms 15872 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 1289 ms 354712 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 22 ms 596 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 887 ms 354616 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 431 ms 354744 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 28 ms 596 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 1091 ms 354724 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 1271 ms 354808 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 1242 ms 353508 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 1294 ms 353588 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 1273 ms 353488 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 1326 ms 353516 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 1223 ms 353556 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 691 ms 307728 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 1358 ms 353496 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'