Submission #931814

#TimeUsernameProblemLanguageResultExecution timeMemory
931814alextodoranChorus (JOI23_chorus)C++17
0 / 100
1 ms2396 KiB
/** _ _ __ _ _ _ _ _ _ |a ||t ||o d | |o | | __ _| | _ | __| _ | | __ |/_ | __ /__\ / _\| **/ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int N_MAX = 2000000; const ll INF = LLONG_MAX; const ld EPS = 1e-9; int N, K; int A[N_MAX + 2]; ld dp[N_MAX + 2]; int cnt[N_MAX + 2]; ll cost[N_MAX + 2]; pair <ld, int> f (int j) { return make_pair(dp[j] + cost[j + 1], cnt[j]); } ll solve (ld pen) { fill(cost + 1, cost + N + 1, 0); deque <int> rel; for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { cost[j] += max(0, (A[i] - i + 1) - j); } pair <ld, int> mn = f(0); for (int j = 1; j <= i - 1; j++) { mn = min(mn, f(j)); } tie(dp[i], cnt[i]) = mn; dp[i] += pen; cnt[i]++; } return (ll) round(dp[N] - pen * cnt[N]); } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(2); cin >> N >> K; string S; cin >> S; for (int i = 0, j = 0; i < N * 2; i++) { if (S[i] == 'A') { A[++j] = i + 1; } } ld l = 0, r = LLONG_MAX; int iter = 200; while (l + EPS < r) { ld mid = (l + r) / 2; solve(mid); if (cnt[N] <= K) { r = mid; } else { l = mid + EPS; } } cout << solve(l) << "\n"; assert(cnt[N] <= K); return 0; }

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:63:34: warning: unused variable 'iter' [-Wunused-variable]
   63 |     ld l = 0, r = LLONG_MAX; int iter = 200;
      |                                  ^~~~
#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...