Submission #767491

#TimeUsernameProblemLanguageResultExecution timeMemory
767491PurpleCrayonChorus (JOI23_chorus)C++17
40 / 100
7032 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; // min CHT with // - slopes decreasing // - query x increasing struct Line { int m, b; int calc(int x) { return m * x + b; } }; struct CHT { deque<Line> lines; void add(int m, int b) { while (sz(lines) >= 2) { auto A = lines.end()[-2]; auto B = lines.end()[-1]; if ((b - A.b) * (A.m - m) <= (B.b - A.b) * (A.m - B.m)) lines.pop_back(); else break; } lines.push_back({m, b}); } int qry(int x) { int ans = MOD; for (auto line : lines) ans = min(ans, line.calc(x)); return ans; /* while (sz(lines) >= 2 && lines[0].calc(x) >= lines[1].calc(x)) { lines.pop_front(); } return lines[0].calc(x); */ } }; 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; } } } vector<int> prv(n, MOD); for (int k = 1; k <= K; k++) { vector<int> nxt(n, MOD); CHT lines; for (int i = 0; i < n; i++) { lines.add(-i, i * i - i + l_use[i] + (i == 0 ? 0 : prv[i-1])); nxt[i] = lines.qry(i) + ps[i]; 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(); }
#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...