Submission #1053685

#TimeUsernameProblemLanguageResultExecution timeMemory
1053685dpsaveslivesJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
11 ms5452 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5+5; int pref[3][MAXN],dp[3][MAXN]; int main(){ int N,K; cin >> N >> K; for(int i = 1;i<=N;++i){ char c; cin >> c; if(c == 'J') pref[0][i]++; else if(c == 'O') pref[1][i]++; else pref[2][i]++; pref[0][i] += pref[0][i-1]; pref[1][i] += pref[1][i-1]; pref[2][i] += pref[2][i-1]; } memset(dp[0],0x3f,sizeof(dp[0])); int cur = 1e9, pos = 0; for(int i = 1;i<=N;++i){ while(pref[0][i]-pref[0][pos] >= K && pos < i){ cur = min(cur,-pos); pos++; } dp[0][i] = cur+i; } memset(dp[1],0x3f,sizeof(dp[1])); cur = 1e9; pos = 0; for(int i = 1;i<=N;++i){ while(pref[1][i]-pref[1][pos] >= K && pos < i){ cur = min(cur,dp[0][pos]-pos); pos++; } dp[1][i] = cur+i; } memset(dp[2],0x3f,sizeof(dp[2])); cur = 1e9; pos = 0; for(int i = 1;i<=N;++i){ while(pref[2][i]-pref[2][pos] >= K && pos < i){ cur = min(cur,dp[1][pos]-pos); pos++; } dp[2][i] = cur+i; } int ans = *min_element(dp[2],dp[2]+N+1) - 3*K; if(ans > 1e7) cout << -1 << "\n"; else cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...