Submission #1333912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333912		KhoaDuy	Tricks of the Trade (CEOI23_trade)	C++20	50 / 100	2817 ms	18180 KiB

trade

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll limit=-1e18;
struct node{
    int delidx=-1,addidx=-1;
};
ll ans=limit;
set<pair<int,int>> se;
ll curr=0;
const int MAXN=3*1e5;
ll pre[MAXN+1];
int c[MAXN+1],s[MAXN+1];
int k;
stack<node> st;
stack<bool> rb;
int L,R;
node Tid;
ll calc(){
    return (curr-(pre[R]-pre[L-1]));
}
void add(int idx){
    node nxt;
    curr+=s[idx];
    se.insert({s[idx],idx});
    nxt.addidx=idx;
    if(se.size()>k){
        int idx2=(*se.begin()).second;
        nxt.delidx=idx2;
        se.erase(se.begin());
        curr-=s[idx2];
    }
    st.push(nxt);
}
void rollback(int cnt){
    for(int bruh=0;bruh<cnt;bruh++){
        node temp=st.top();
        st.pop();
        if(!rb.top()){
            L++;
        }
        else{
            R--;
        }
        if(temp.delidx!=-1){
            se.insert({s[temp.delidx],temp.delidx});
            curr+=s[temp.delidx];
        }
        if(temp.addidx!=-1){
            se.erase({s[temp.addidx],temp.addidx});
            curr-=s[temp.addidx];
        }
        rb.pop();
    }
}
void moveL(int cnt){
    for(int bruh=0;bruh<cnt;bruh++){
        L--;
        if(L<=R){
            add(L);
        }
        else{
            st.push(Tid);
        }
        rb.push(false);
    }
}
void moveR(int cnt){
    for(int bruh=0;bruh<cnt;bruh++){
        R++;
        if(L<=R){
            add(R);
        }
        else{
            st.push(Tid);
        }
        rb.push(true);
    }
}
void dnc(int l,int r,int optl,int optr){
    // cout << "HERE " << l << ' ' << r << ' ' << optl << ' ' << optr << endl;
    // cout << "??? " << L << ' ' << R << endl;
    int mid=((l+r)>>1);
    moveL(r-mid);
    int optm=-1;
    ll val=limit;
    for(int i=optl;i<=optr;i++){
        ll nxt=calc();
        if(i-mid+1>=k&&nxt>val){
            val=nxt;
            optm=i;
        }
        if(i+1<=optr){
            moveR(1);
        }
    }
    ans=max(ans,val);
    rollback(optr-optl+r-mid);
    if(l<=mid-1){
        moveL(r-mid+1);
        dnc(l,mid-1,optl,optm);
        rollback(r-mid+1);
    }
    if(mid+1<=r){
        moveR(optm-optl);
        dnc(mid+1,r,optm,optr);
        rollback(optm-optl);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen("input.txt","r")){
        freopen("input.txt","r",stdin);
    }
    int n;
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> c[i];
        pre[i]=pre[i-1]+c[i];
    }
    for(int i=1;i<=n;i++){
        cin >> s[i];
    }
    L=n-k+1,R=k;
    for(int i=L;i<=R;i++){
        add(i);
    }
    dnc(1,n-k+1,k,n);
    cout << ans << endl;
    for(int i=0;i<n;i++){
        cout << '0';
    }
}

Compilation message (stderr)

trade.cpp: In function 'int main()':
trade.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 5 / 10
• Subtask 3: 5 / 10
• Subtask 4: 10 / 25
• Subtask 5: 25 / 45