| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037744 |
2024-07-29T07:36:00 Z |
ㅇㅇ(223.39)(#11011) |
Chorus (JOI23_chorus) |
C++17 |
|
1 ms |
2396 KB |
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using db=double;
using pll=array<ll,2>;
using tll=array<ll,3>;
const ll inf=1e18;
const int N=1000005;
int n,k,a[N],m,f[N];
string s;
ll S[N];
pll dp[N];
ll base,ans;
struct ConvexHullTrick{
tll L[N];
int sz,p;
db cross(tll a,tll b){
return (db)(b[1]-a[1])/(a[0]-b[0]);
}
void add_line(tll l){
while(sz>=2&&cross(L[sz-1],L[sz])>=cross(L[sz],l)) sz--;
L[++sz]=l;
p=min(p,sz);
}
pll qry(ll x){
if(!sz) return {-1,-1};
while(p<sz&&cross(L[p],L[p+1])<=x) p++;
return {L[p][0]*x+L[p][1],L[p][2]};
}
}CHT;
pll Do(ll C){
dp[0]={0,0};
deque<int> dq;
dq.push_back(0);
CHT.sz=0; CHT.p=1;
for(int i=1;i<=n;i++){
dp[i]={inf,inf};
while(dq.size()&&dq.front()<=f[i]-2) dq.pop_front();
if(dq.size()) dp[i]={dp[dq.front()][0]+C,dp[dq.front()][1]+1};
for(int j=max(0,f[i-1]-1);j<=f[i]-2;j++) CHT.add_line({-j,dp[j][0]-(ll)j*(j+1)/2+S[j]+C,dp[j][1]+1});
pll Q=CHT.qry(i);
if(Q[1]!=-1) dp[i]=min(dp[i],{Q[0]+(ll)(f[i]-1)*i+(ll)(i-1)*i/2-S[f[i]-1],Q[1]});
while(dq.size()&&dp[dq.back()]>=dp[i]) dq.pop_back();
dq.push_back(i);
}
return dp[n];
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k>>s;
for(int i=1;i<=2*n;i++) if(s[i-1]=='B') a[++m]=i;
for(int i=1;i<=n;i++) if(a[i]<2*i){
base+=2*i-a[i];
a[i]=2*i;
}
for(int i=1;i<=n;i++) S[i]=S[i-1]+a[i];
f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1];
while(i+f[i]-a[f[i]]>0) f[i]++;
}
ll L=-1e10,R=1e10;
while(L<=R){
ll M=(L+R)>>1;
auto [dp,cnt]=Do(M);
ans=max(ans,dp-k*M);
if(cnt<=k) R=M-1;
else L=M+1;
}
cout<<base+ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
