제출 #776299

#제출 시각아이디문제언어결과실행 시간메모리
776299ArturgoChorus (JOI23_chorus)C++14
0 / 100
1 ms256 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int INFINI = 1e18; int N, K; string types; vector<int> ouvrantes, fermantes; vector<int> derFermantes, cumOuvrAvant; // bornes incluses int cout_transition(int i, int j) { int df = derFermantes[j]; if(df < i) return 0; int deb = i; int fin = min(j, df); return (j + 1) * (fin - deb + 1) - (cumOuvrAvant[fin + 1] - cumOuvrAvant[deb]); } pair<int, int> calc(int coutGroupe) { vector<pair<int, int>> dyns; dyns.push_back({0, 0}); for(int pos = 0;pos < N;pos++) { pair<int, int> mini = {INFINI, 0}; for(int deb = 0;deb <= pos;deb++) { mini = min(mini, { cout_transition(deb, pos) + dyns[deb].first + coutGroupe, dyns[deb].second + 1 }); } dyns.push_back(mini); } return dyns.back(); } signed main() { cin >> N >> K; cin >> types; cumOuvrAvant.push_back(0); for(int i = 0;i < 2 * N;i++) { if(types[i] == 'A') { ouvrantes.push_back(i); derFermantes.push_back((int)fermantes.size() - 1); } else { fermantes.push_back(i); cumOuvrAvant.push_back( cumOuvrAvant.back() + (int)ouvrantes.size() ); } } int deb = 0, fin = 1000ll * 1000 * 1000 * 1000ll; while(fin - deb > 1) { int mil = (deb + fin) / 2; pair<int, int> solOpt = calc(mil - 1); if(solOpt.second <= K) { fin = mil; } else { deb = mil; } } pair<int, int> solOpt = calc(deb); cout << solOpt.first - deb * solOpt.second << 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...
#Verdict Execution timeMemoryGrader output
Fetching results...