Submission #1053540

#TimeUsernameProblemLanguageResultExecution timeMemory
1053540sofijavelkovskaBoarding Passes (BOI22_passes)C++17
60 / 100
2099 ms8448 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=1e5, MAXK=15; const long long INF=1e18; string s; int n, k; vector<vector<int> > groups; double memo[(1<<MAXK)]; double inv[MAXN+1]; double dp(int mask) { if (memo[mask]!=-1) return memo[mask]; if (mask==(1<<k)-1) return memo[mask]=0; int prefix[n]={0}; for (int i=0; i<k; i++) { if (!(mask&(1<<i))) continue; for (auto x : groups[i]) prefix[x]=1; } for (int i=1; i<n; i++) prefix[i]=prefix[i-1]+prefix[i]; int m=prefix[n-1]; double answer=INF; for (int i=0; i<k; i++) { if (mask&(1<<i)) continue; double mintotal=INF; long long maininv=0; int g=groups[i].size(); for (auto x : groups[i]) if (x!=0) maininv=maininv+prefix[x-1]; mintotal=min(mintotal, inv[g]+maininv); for (int j=g-1; j>=0; j--) { int x=groups[i][j]; if (x!=0) maininv=maininv-prefix[x-1]; maininv=maininv+(m-prefix[x]); mintotal=min(mintotal, inv[j]+inv[g-j]+maininv); } answer=min(answer, dp(mask|(1<<i))+mintotal); } return memo[mask]=answer; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> s; n=s.size(); map<char, vector<int> > groupsbychar; for (int i=0; i<n; i++) groupsbychar[s[i]].push_back(i); for (auto t : groupsbychar) groups.push_back(t.second); k=groups.size(); for (int i=0; i<=n; i++) inv[i]=(double)i*(i-1)/4; for (int i=0; i<(1<<k); i++) memo[i]=-1; cout << fixed << setprecision(5) << dp(0); 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...