Submission #1202300

#TimeUsernameProblemLanguageResultExecution timeMemory
1202300UnforgettableplBoarding Passes (BOI22_passes)C++20
60 / 100
1297 ms5004 KiB
#pragma GCC optimize("Ofast","unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); const int G = 10; vector<vector<int>> groups(G); string s; cin >> s; int N = s.size(); for(int i=0;i<N;i++){ groups[s[i]-'A'].emplace_back(i+1); } vector<int> DP((1<<G),1e12); DP[0]=0; for(int mask=1;mask<(1<<G);mask++){ vector<pair<int,int>> arr; int tot = 0; for(int x=0;x<G;x++)if(mask&(1<<x)){ for(int&i:groups[x])arr.emplace_back(i,x); tot+=groups[x].size(); } ranges::sort(arr); for(int top=0;top<G;top++)if(mask&(1<<top)){ int ans = 0; int currOther = 0; int currMine = 0; for(auto&[i,type]:arr){ if(type!=top){ currOther++; continue; } ans+=min(currMine+2ll*currOther,(int)((int)groups[top].size()-1ll-currMine+2ll*(tot-groups[top].size()-currOther))); currMine++; } DP[mask]=min(DP[mask],DP[mask^(1<<top)]+ans); } } cout << DP[(1<<G)-1]/2; if(DP[(1<<G)-1]&1)cout<<".5"; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...