Submission #963053

#TimeUsernameProblemLanguageResultExecution timeMemory
963053RaresFelixChorus (JOI23_chorus)C++17
0 / 100
2 ms348 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("O3") //#pragma GCC target("avx,avx2,fma") #define sz(x) int((x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ld = long double; // or double, if TL is tight using str = string; using ii = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; const ll INF = 1e18; struct CHT { int p = 0; vector<pair<ll, ll> > V; void insert(ll a, ll b) { /// ax + b //a va scadea mereu while(V.size() > 1) { auto [a1, b1] = V.end()[-1]; auto [a2, b2] = V.end()[-2]; if((b2 - b) * (a1 - a2) <= (b2 - b1) * (a - a2)) V.pop_back(); else break; } V.push_back({a, b}); } ll query(ll x) { if(V.empty()) return INF; auto eval = [&](int i) { return V[i].first * x + V[i].second; }; while(p + 1 < V.size() && eval(p + 1) <= eval(p)) ++p; return eval(p); } }; int main() { cin.tie(0); ios_base::sync_with_stdio(0); int n, k; cin >> n >> k; string s0, s; cin >> s0; ll re0 = 0; int nrB = 0, sum = 0; for(auto it : s0) { if(it == 'A') { ++sum; s += 'A'; re0 += nrB; if(nrB && sum) { s += 'B'; --nrB; --sum; } } else { if(sum) { s += 'B'; --sum; } else { ++nrB; } } } vi A, P(n + 1); vll SA; P[0] = -1; for(auto it : s) { if(it == 'A'){ A.push_back(nrB); if(SA.empty()) SA.push_back(A.back()); else SA.push_back(A.back() + SA.back()); } else { ++nrB; P[nrB] = (int)A.size() - 1; } } vll SAP(n); for(int i = 0; i < n; ++i) { SAP[i] = 0; if(P[i] != -1) SAP[i] = SA[P[i]]; } auto cost = [&](ll st, ll dr) { return st * P[st] - SAP[st] + SA[dr] - st * dr; }; vector<vll> DP(n, vll(k + 1, INF)); vector<CHT> Sol(k + 1); for(int i = 0; i < n; ++i) { DP[i][1] = cost(0, i); if(i) Sol[1].insert(-i, i * P[i] - SAP[i] + DP[i - 1][1]); for(int j = 2; j <= k; ++j) { if(i) Sol[j].insert(-i, DP[i - 1][j] + i * P[i] - SAP[i]); DP[i][j] = Sol[j - 1].query(i) + SA[i]; } } ll re = INF; for(auto it : DP[n - 1]) re = min(re, it); cout << re + re0 << "\n"; return 0; }

Compilation message (stderr)

chorus.cpp: In member function 'll CHT::query(ll)':
chorus.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while(p + 1 < V.size() && eval(p + 1) <= eval(p)) ++p;
      |               ~~~~~~^~~~~~~~~~
#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...