Submission #1217369

#TimeUsernameProblemLanguageResultExecution timeMemory
1217369MuhammadSaramBoarding Passes (BOI22_passes)C++20
0 / 100
3 ms1288 KiB
#include <bits/stdc++.h> using namespace std; #define dd double #define all(v) v.begin(), v.end() const int M = 10001, N = 7; dd e[M],val[N][1<<N][101]; vector<int> a[N]; signed main() { ios::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); cout<<fixed<<setprecision(10); for (int i=2;i<M;i++) e[i]=i*(i-1)/4.0; string s; cin>>s; int n=s.size(); for (int i=0;i<n;i++) a[s[i]-'A'].push_back(i); if (a[0].size()==n) { cout<<e[n/2]+e[n-n/2]<<endl; return 0; } vector<int> v; for (int i=0;i<N;i++) v.push_back(i); for (int i=0;i<N;i++) for (int m=0;m<(1<<N);m++) for (int k=0;k<=a[i].size();k++) { if (m>>i&1) continue; for (int j=0;j<N;j++) { if ((m>>j)%2==0) continue; for (int l=0;l<k;l++) val[i][j][k]+=lower_bound(all(a[j]),a[i][l])-begin(a[j]); for (int l=k;l<a[i].size();l++) val[i][j][k]+=a[j].size()-(lower_bound(all(a[j]),a[i][l])-begin(a[j])); } } dd ans=n*(n-1)/2; do { int m=0; dd vl=0; for (int i:v) { dd mn=n*(n-1)/2; int sz=a[i].size(); for (int k=0;k<=sz;k++) mn=min(mn,val[i][m][k]+e[k]+e[sz-k]); vl+=mn,m+=(1<<i); } ans=min(ans,vl); }while(next_permutation(all(v))); cout<<ans<<endl; 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...