#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
vector<int> a,b,pre,lx;
int n;
typedef pair<int,int> pii;
bool check(pii a,pii b,pii c){
return (b.sc-a.sc)*(b.fs-c.fs)>(c.sc-b.sc)*(a.fs-b.fs);
}
bool check2(pii a,pii b,int c){
return a.fs*c+a.sc>b.fs*c+b.sc;
}
void check3(pii& a,pii b){
a=min(a,b);
}
pii get(int p){
vector<pii> dp(n+1,{1e18,1e18});
//dp[i] = min(dp[j]+pre[i]+(cost)-b[j+1]*i);
// -2 1 3 4 5 8 11
// -1 2 6 7 9 10 12
// 6 -> 1 = dp[1]+pre_a[6]+(6-1+6-3+6-4+6-5)-6*6 = 2+5 = 7+dp[1]
// 4 -> 1: because 5 < 6, so the cost is 0
// when 1 is available, lx[1] = 4 and update with 4*6-pre[4];
// s dec, qu inc;
//
dp[0]={0,0};
deque<pii> li;
deque<int> dz;
int f=1;
cout << p << "\n";
for(int i=1;i<=n;i++){
while(f<i && lx[f]<i){
pii ad(-2*b[f]+2*lx[f]+1,2*(dp[f-1].fs+(i-1)*b[f]-pre[i-1])-lx[f]*lx[f]-lx[f]);
while(li.size()>=2 && check(li[li.size()-2],li.back(),ad)){
li.pop_back();
dz.pop_back();
}
cout << "u: " << ad.fs << " " << ad.sc << "\n";
li.push_back(ad);
dz.push_back(f-1);
f++;
}
while(li.size()>=2 && check2(li[0],li[1],i)){
li.pop_front();
dz.pop_front();
}
if(li.size()){
dp[i].fs=(li[0].fs*i+li[0].sc+2*pre[i]+2*p-i*i)/2;
dp[i].sc=dp[dz[0]].sc+1;
}
else{
dp[i]={p,1};
}
check3(dp[i],pii(dp[f-1].fs+p,dp[f-1].sc+1));
cout << dp[i].fs << " " << dp[i].sc << "\n";
}
cout << '\n';
return dp[n];
}
signed main(){
AquA;
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
int k;
cin >> n >> k;
string s;
cin >> s;
int ans=0,cnt=0,cs=0,tmp=0;
a.push_back(-2);
b.push_back(-1);
for(int i=0;i<2*n;i++){
if(s[i]=='A'){
cnt++;
a.push_back(cs);
ans+=i-cs;
cs++;
if(tmp>0){
tmp--;
b.push_back(cs);
cnt--;
cs++;
}
}
else{
if(cnt==0){
tmp++;
}
else{
cnt--;
b.push_back(cs);
cs++;
}
}
}
pre=a;
lx.resize(n+2);
a.push_back(998244353);
b.push_back(998244354);
for(int i=1;i<=n;i++){
lx[i]=lx[i-1];
while(lx[i]+1<a.size() && a[lx[i]+1]<=b[i]){
lx[i]++;
}
}
for(int i=2;i<=n;i++){
pre[i]+=pre[i-1];
}
for(auto h:a){
cout << h << " ";
}
cout << "\n";
for(auto h:b){
cout << h << " ";
}
cout << "\n";
int l=0,r=1e18;
while(r>l){
int m=(l+r)/2;
auto u=get(m);
if(u.sc<=k){
r=m;
}
else{
l=m+1;
}
}
auto z=get(l);
cout << ans << '\n';
cout << ans+(z.fs-k*l) << "\n";
return 0;
}
Compilation message
chorus.cpp: In function 'int main()':
chorus.cpp:107:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | while(lx[i]+1<a.size() && a[lx[i]+1]<=b[i]){
chorus.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | freopen("1.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
chorus.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen("1.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
