Submission #1215271

#TimeUsernameProblemLanguageResultExecution timeMemory
1215271salmonChorus (JOI23_chorus)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; int N, K; pair<long double,int> memo[5100]; long long int pre[5100][5100]; int in[10100]; int bin[10100]; string s; long long int inf = 1.1e18; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> N >> K; cin >> s; int a = 1; int b = 1; for(int i = 0; i < N * 2; i++){ if(s[i] == 'A'){ bin[a] = b; a++; } else{ b++; } } for(int i = 1; i <= N; i++){ pre[i][i - 1] = 0; for(int j = i; j <= N; j++){ pre[i][j] = pre[i][j - 1] + max(0,bin[j] - i ); } } long double s = 0; long double e = 1e13; for(int i = 0; i < 100; i++){ long double m = (s + e)/2; for(int i = 0; i <= N; i++){ memo[i] = {inf,1}; } memo[0] = {0,0}; for(int i = 1; i <= N; i++){ for(int k = i; k >= 1; k--){ memo[i] = min(memo[i], {memo[k - 1].first + pre[k][i] + m, memo[k - 1].second + 1} ); } } /*for(int i = 1; i <= N; i++){ printf("%lld\n",memo[i][K]); }*/ if(i == 100) break; if(memo[N].second > K){ s = m; } else{ e = m; } } printf("%lld",(long long int)(memo[N].first - memo[N].second * s + 0.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...
#Verdict Execution timeMemoryGrader output
Fetching results...