제출 #1205843

#제출 시각아이디문제언어결과실행 시간메모리
1205843lightonBoarding Passes (BOI22_passes)C++17
25 / 100
2 ms584 KiB
#include<bits/stdc++.h> #define pb push_back #define all(v) v.begin(),v.end() #define forf(i,s,e) for(int i = s; i<=e; i++) #define forb(i,s,e) for(int i = s; i>=e; i--) #define idx(i,v) lower_bound(all(v),i)-v.begin() #define comp(v) v.erase(unique(all(v)),v.end()) #define sz(v) (int)v.size() #define fs first #define se second #define SP << " " << #define LN << "\n" #define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false); using namespace std; typedef long long ll; ll inf = 1e18; int N,M; string S; vector<char> chars; vector<int> pos[16]; int G[100001]; vector<double> f[16][16]; double dp[1<<15]; double eval(int now, int bit, int idx){ double ret = 0; forf(i,0,M-1){ if(!(bit & ( 1<<i))) continue; if(i==now) ret += f[now][i][idx]/2; else ret += f[now][i][idx]; } return ret; } double calc(int now, int bit){ int l = -1, r = sz(f[now][now])-1; while(l+1<r){ int m = l+r>>1; if(eval(now,bit,m) < eval(now,bit,m+1)) r = m; else l = m; } return eval(now,bit,r); } int main(){ cin>>S; N = sz(S); forf(i,0,N-1) chars.pb(S[i]); sort(all(chars)), comp(chars); forf(i,0,N-1) G[i] = idx(S[i], chars), pos[G[i]].pb(i); M = sz(chars); forf(i,0,M-1){ forf(j,0,M-1){ f[i][j].resize(sz(pos[i])+1,0); for(auto u : pos[i]){ f[i][j][0] += pos[j].end() - upper_bound(all(pos[j]), u); } int idx = 1; for(auto u : pos[i]){ f[i][j][idx] = f[i][j][idx-1]; f[i][j][idx] -= pos[j].end() - upper_bound(all(pos[j]),u); f[i][j][idx] += lower_bound(all(pos[j]), u) - pos[j].begin(); idx++; } } } forf(i,1,(1<<M)-1) dp[i] = inf; forf(now,1,(1<<M)-1){ forf(b,0,M-1){ if(!(now&(1<<b))) continue; int prv = now^(1<<b); dp[now] = min(dp[now], dp[prv] + calc(b,now)); } } cout<< dp[(1<<M)-1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...