Submission #767429

#TimeUsernameProblemLanguageResultExecution timeMemory
767429PurpleCrayonChorus (JOI23_chorus)C++17
40 / 100
7095 ms468 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 5e3+10, MOD = 1e9+7; int n, K, small[N]; int ps[N], l_use[N]; vector<int> one, two; void solve() { cin >> n >> K; for (int i = 0; i < 2 * n; i++) { char c; cin >> c; if (c == 'A') one.push_back(i); else two.push_back(i); } for (int i = 0; i < n; i++) { small[i] = lower_bound(two.begin(), two.end(), one[i]) - two.begin(); } for (int i = 0; i < n; i++) { ps[i] = small[i] + (i ? ps[i-1] : 0); l_use[i] = -(i ? ps[i-1] : 0); for (int j = i; j < n; j++) { if (small[j] < i) { l_use[i] -= small[j] - i; } } } auto COST = [&](int l, int r) { // - l * r + l * l - l + l_use[l] + ps[r] return ps[r] + l_use[l] - l * (r - l + 1); }; vector<int> prv(n, MOD); for (int k = 1; k <= K; k++) { vector<int> nxt(n, MOD); vector<pair<int, int>> lines; for (int i = 0; i < n; i++) { lines.push_back({-i, i * i - i + l_use[i] + (i == 0 ? 0 : prv[i-1])}); for (auto [m, b] : lines) { nxt[i] = min(nxt[i], i * m + b + ps[i]); } /* for (int l = i; l >= 0; l--) { nxt[i] = min(nxt[i], COST(l, i) + (l == 0 ? 0 : prv[l-1])); } */ int l = small[i]; if (l <= i) { nxt[i] = min(nxt[i], (l == 0 ? 0 : prv[l-1])); } } swap(prv, nxt); } cout << prv[n-1] << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) solve(); }

Compilation message (stderr)

chorus.cpp: In function 'void solve()':
chorus.cpp:35:10: warning: variable 'COST' set but not used [-Wunused-but-set-variable]
   35 |     auto COST = [&](int l, int r) {
      |          ^~~~
#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...