Submission #573979

#	Time	Username	Problem	Language	Result	Execution time	Memory
573979		kshitij_sodani	Boarding Passes (BOI22_passes)	C++14	100 / 100	384 ms	343332 KiB

passes

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
 
 
llo dp[1<<16];
llo it[100001];
llo ans[100001];
llo vis[100001];
vector<llo> pre[20];

llo pre4[15][15][100001];

llo pre2[15][15][100001];
llo pre3[15][100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin>>s;
	llo m=0;
	llo n=s.size();
	for(llo i=0;i<n;i++){
		m=max(m,(llo)(s[i]-'A'+1));
		it[i]=s[i]-'A';
		pre[it[i]].pb(i);
	}
	for(llo i=0;i<(1<<m);i++){
		dp[i]=1e18;
	}
	dp[0]=0;
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(i==j){
				continue;
			}
			int su=0;
			for(int ii=0;ii<n;ii++){
				pre4[i][j][ii+1]=pre4[i][j][ii];

				if(it[ii]==i){
					pre4[i][j][ii+1]+=su;
				//	su++;
				}
				else if(it[ii]==j){
					su+=2;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			pre3[j][i+1]=pre3[j][i];
			if(it[i]==j){
				pre3[j][i+1]+=2;
			}
		}
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			if(i==j){
				continue;
			}
			int su=0;
			for(int ii=n-1;ii>=0;ii--){
				pre2[i][j][ii]=pre2[i][j][ii+1];

				if(it[ii]==i){
					pre2[i][j][ii]+=su;
					//su++;
				}
				else if(it[ii]==j){
					su+=2;
				}
			}
		}
	}
	//cout<<pre[1].size()<<endl;
	for(llo i=0;i<(1<<m);i++){
		vector<int> ss;
		for(int j=0;j<m;j++){
			if((1<<j)&i){
				ss.pb(j);
			}
		}
		/*for(llo j=0;j<n;j++){
			if((1<<it[j])&i){
				vis[j+1]=2;
			}
			else{
				vis[j+1]=0;
			}
			vis[j+1]+=vis[j];
		}*/
		for(llo j=0;j<m;j++){
			if((1<<j)&i){
				continue;
			}
			if(pre[j].size()==0){
				dp[i+(1<<j)]=min(dp[i+(1<<j)],dp[i]);
				continue;
			}
			llo low=-1;
			llo xx=pre[j].size();
			for(int jj=17;jj>=0;jj--){
				if(low+(1<<jj)<(llo)pre[j].size()){
					//check if left<=right
					int ind=pre[j][low+(1<<jj)];
					llo su=0;
					llo su2=0;
					for(auto ii:ss){
						su+=pre3[ii][ind];
						su2+=pre3[ii][n]-pre3[ii][ind];
					}
					su+=low+(1<<jj);
					su2+=(xx-(low+(1<<jj))-1);
					if(su<=su2){
						low+=(1<<jj);
					}
				
				}
			}

			llo cur=0;

			cur+=((low*(low+1)))/2;
			llo low2=xx-low-1;
			cur+=((low2-1)*(low2))/2;
			llo ind=-1;

		//	cout<<cur<<":"<<low+1<<":"<<low2<<endl;
			if(low>=0){
				ind=pre[j][low];
			}
			for(auto jj:ss){
				cur+=pre4[j][jj][ind+1];
				
				cur+=pre2[j][jj][ind+1];
			}
			//cout<<i<<":"<<j<<":"<<low<<endl;
			dp[i+(1<<j)]=min(dp[i+(1<<j)],dp[i]+cur);
			/*llo le=pre[j].size();
			llo cur2=dp[i];
			llo su=0;
			for(auto jj:pre[j]){
				llo cur3=min(su+vis[jj],le-su-1+vis[n]-vis[jj]);
				cur2+=cur3;
				su++;
				//cout<<j<<":"<<cur3<<endl;
			}
			*/
		}
	}
	llo aa=dp[(1<<m)-1];
//	cout<<aa<<endl;
	if(aa%2==0){
		cout<<(aa/2)<<endl;
	}
	else{
		cout<<(aa/2)<<".5"<<endl;
		/*long double xx=aa;
		xx/=(long double)2;
		cout<<setprecision(2)<<xx<<endl;*/
	}

	
 
 
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40