Submission #956641

#	Time	Username	Problem	Language	Result	Execution time	Memory
956641		huutuan	Chorus (JOI23_chorus)	C++17	0 / 100	3 ms	2464 KiB

chorus

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

struct Line{
   mutable int k, m, p, cnt;
   bool operator<(const Line &a){ return k<a.k; }
   bool operator<(int x){ return p<x; }
};

const int inf=1e18;

struct LineContainer: vector<Line>{
   int id;
   int div(int a, int b){
      return a/b-((a^b)<0 && a%b);
   }
   bool isect(iterator x, iterator y){
      if (y==end()) return x->p=inf, 0;
      if (x->k==y->k) x->p=x->k>=y->k?inf:-inf;
      else x->p=div(y->m-x->m, x->k-y->k);
      return x->p>=y->p;
   }
   void add(int k, int m, int cnt){
      auto z=insert(end(), {k, m, 0, cnt}), y=z++, x=y;
      while (isect(y, z)) z=erase(z);
      if (x!=begin() && isect(--x, y)) erase(y);
      while ((y=x)!=begin() && (--x)->p>=y->p) erase(y);
      id=min((int)size()-1, id+1);
   }
   LineContainer(){
      id=0;
   }
   pair<int, int> query(int x){
      while (id && !(*(begin()+id-1)<x)) --id;
      return {(begin()+id)->k*x+(begin()+id)->m, (begin()+id)->cnt};
   }
};

const int N=1e6+10;
int n, k, a[N], pf[N];
pair<int, int> f[N];
string s;

pair<int, int> dp(int penalty){
   LineContainer cht;
   for (int i=1; i<=n; ++i) f[i]={inf, 0};
   f[0]={0, 0};
   cht.add(0, 0, 0);
   for (int i=1, j=0; i<=n; ++i){
      while (j<i && a[j+1]<i) ++j;
      auto tmp=cht.query(i);
      f[i]={max(0ll, -tmp.first+j*i-pf[j])+penalty, tmp.second+1};
      cht.add(i, -f[i].first-pf[i], f[i].second);
   }
   return f[n];
}

void solve(){
   cin >> n >> k >> s;
   for (int i=0, j=1; i<n*2; ++i){
      if (s[i]=='A') ++a[j];
      else a[j+1]=a[j], ++j;
   }
   partial_sum(a, a+n+1, pf);
   dp(0);
   int l=0, r=inf;
   while (l<=r){
      int mid=(l+r)>>1;
      auto tmp=dp(mid);
      if (tmp.second<=k) r=mid-1;
      else l=mid+1;
   }
   auto ans=dp(l);
   cout << ans.first-ans.second*l;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13