Submission #953512

#TimeUsernameProblemLanguageResultExecution timeMemory
953512PM1Boarding Passes (BOI22_passes)C++17
0 / 100
2060 ms2908 KiB
#include <bits/stdc++.h> using namespace std; #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,sum[(1<<mxg)],num[mxg+5],rsum[(1<<mxg)],zz=2; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>s; n=s.size(); 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; for(int j=0;j<(1<<mxg);j++){ if(j&(1<<(x-1))){ rsum[j]+=z; } } } for(int i=0;i<n;i++){ int x=s[i]; x=a[x]; for(int j=0;j<(1<<cnt);j++){ if(j&(1<<(x-1)))continue; res[j][x]+=min(sum[j]+num[x],rsum[j]+all[x]-num[x]-z); } for(int j=0;j<(1<<cnt);j++){ if(j&(1<<(x-1))){ rsum[j]-=z; sum[j]+=z; } } num[x]+=z; } 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]+res[y][j+1]); } } } cout<<dp[(1<<cnt)-1]/2; if(dp[(1<<cnt)-1]%2) cout<<".5"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...