제출 #1301840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301840		loom	Tricks of the Trade (CEOI23_trade)	C++20	50 / 100	4139 ms	16092 KiB

trade

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

const int N = 250001;
int k, cl, cr, sum, ans = -inf;
int c[N], s[N];
multiset<int> in, out;

void add(int i){
   sum -= c[i];
   int x = s[i];
   auto it = in.begin();

   if(in.size() < k){
      in.insert(x);
      sum += x;
   }
   else if(x > *it){
      sum -= *it;
      out.insert(*it);
      in.erase(it);
      in.insert(x);
      sum += x;
   }
   else{
      out.insert(x);
   }
}

void del(int i){
   sum += c[i];
   int x = s[i];

   if(out.find(x) != out.end()){
      out.erase(out.find(x));
   }
   else{
      in.erase(in.find(x));
      sum -= x;

      if(!out.empty()){
         auto it = prev(out.end());

         sum += *it;
         in.insert(*it);
         out.erase(it);
      }
   }
}

void seg(int l, int r){
   while(cl < l){
      del(cl);
      cl++;
   }
   while(cl > l){
      cl--;
      add(cl);
   }
   while(cr < r){
      cr++;
      add(cr);
   }
   while(cr > r){
      del(cr);
      cr--;
   }
}

void solve(int l, int r, int opl, int opr){
   if(l > r) return;

   int m = (l+r)/2;
   int ogl = cl, ogr = cr;

   seg(m, max(m, opl));
   int mx = -inf, op = opr;

   if(cr - m + 1 >= k){
      mx = sum;
      op = cr;
   }
   
   while(cr < opr){
      cr++;
      add(cr);
      if(cr-m+1 < k) continue;
      
      if(mx < sum){
         mx = sum;
         op = cr;
      }
   }

   ans = max(ans, mx);

   solve(l, m-1, opl, op);
   solve(m+1, r, op, opr);

   seg(ogl, ogr);
}

void solve(){
   int n;
   cin>>n>>k;

   for(int i = 1; i <= n; i++) cin>>c[i];
   for(int i = 1; i <= n; i++) cin>>s[i];

   cl = 1, cr = n;
   for(int i = 1; i <= n; i++) add(i);

   solve(1, n, 1, n);
   cout<<ans;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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