Submission #1094341

#TimeUsernameProblemLanguageResultExecution timeMemory
1094341_8_8_Chorus (JOI23_chorus)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e3 + 12, MOD = (int)1e9 + 7; int n, k, x[N], y[N], pref[ 2 * N], col[N], opt[N]; ll dp[N], c[N][N]; void prec() { for(int i = 1; i <= n; i++) { for(int j = i; j >= 1; j--) { c[j][i] = c[j + 1][i]; if(y[j] <= x[i]) { c[j][i] += pref[x[i]] - pref[y[j] - 1];; } } } for(int i = 1; i < n; i++) { for(int j = 1; j < n; j++) { assert(c[i][j + 1] + c[i + 1][j] >= c[i][j] + c[i + 1][j + 1]); } } } pair<ll, ll> calc_slow(ll pen) { for(int i = 1; i <= n; i++) { dp[i] = 1e18; col[i] = n + 1; for(int j = i; j >= 1; j--) { if(y[j] > x[i]) continue; if(dp[j - 1] + c[j][i] + pen <= dp[i]) { dp[i] = dp[j - 1] + c[j][i] + pen; col[i] = col[j - 1] + 1; opt[i] = j; } } } return {dp[n], col[n]}; } pair<ll, ll> calc(ll pen) { for(int i = 1; i <= n; i++) { } } void test() { cin >> n >> k; int _x = 0, _y = 0; for(int i = 1; i <= n + n; i++) { char a; cin >> a; pref[i] = pref[i - 1]; if(a == 'A') { x[++_x] = i; pref[i]++; } else { y[++_y] = i; } } prec(); ll l = -1, r = 1e12, res; while(r - l > 1) { ll mid = (l + r) / 2; auto [val, t] = calc_slow(mid); if(t <= k) { r = mid; res = val - k * 1ll * mid; } else { l = mid; } } cout << res << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; while(t--) test(); return 0; }

Compilation message (stderr)

chorus.cpp: In function 'std::pair<long long int, long long int> calc(ll)':
chorus.cpp:44:1: warning: no return statement in function returning non-void [-Wreturn-type]
   44 | }
      | ^
#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...