Submission #823799

#TimeUsernameProblemLanguageResultExecution timeMemory
823799PoonYaPatBoarding Passes (BOI22_passes)C++14
60 / 100
2066 ms1812 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll ans,dp[1<<15]; //2 times expected value int m,n,g[100005]; vector<int> group[15]; ll cal(ll a) { return a*(a-1)/2; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); string s; cin>>s; n=s.size(); for (int i=0; i<(1<<15); ++i) dp[i]=2e15; map<char,int> mp; for (int i=0; i<n; ++i) mp[s[i]]=0; for (auto k : mp) mp[k.first]=m++; for (int i=0; i<n; ++i) group[mp[s[i]]].push_back(i), g[i]=mp[s[i]]; dp[0]=0; for (int mask=1; mask<(1<<m); ++mask) { //find dp[mask] bool have[15]; for (int i=0; i<m; ++i) { if (mask&(1<<i)) have[i]=true; else have[i]=false; } for (int i=0; i<m; ++i) { if (mask&(1<<i)) { //consider case i is the last boarding group to put in ll cnt_back=0,sum_back=0,cnt_front=0,sum_front=0,cb=0,cf=0; for (int x=n-1; x>=0; --x) { if (have[g[x]]) { if (g[x]!=i) ++cnt_back; else sum_back+=cnt_back, ++cb; } } dp[mask]=min(dp[mask],dp[mask^(1<<i)]+cal(cb)+2*sum_back); //all get in from back for (int x=0; x<n; ++x) { //people number 0 to x get in from front if (have[g[x]]) { if (g[x]!=i) { ++cnt_front; --cnt_back; } else { ++cf; --cb; sum_front+=cnt_front; sum_back-=cnt_back; dp[mask]=min(dp[mask],dp[mask^(1<<i)]+cal(cf)+cal(cb)+2*sum_back+2*sum_front); } } } } } } cout<<dp[(1<<m)-1]/2; if (dp[(1<<m)-1]%2==1) cout<<".5"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...