oj.uz

Submission #956651

# Submission time Handle Problem Language Result Execution time Memory
956651 2024-04-02T09:42:46 Z huutuan Chorus (JOI23_chorus) C++17
0 / 100
 2 ms 2648 KB 
#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)) isect(x, erase(y));
      while ((y=x)!=begin() && (--x)->p>=y->p) isect(x, erase(y));
   }
   LineContainer(){
      id=0;
   }
   pair<int, int> query(int x){
      while ((begin()+id)->operator<(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=1e9;
   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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2392 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2392 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2392 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2392 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2392 KB Output isn't correct
7 Halted 0 ms 0 KB -