제출 #1176324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176324		pera	쌀 창고 (IOI11_ricehub)	C++20	17 / 100	0 ms	328 KiB

ricehub

#include<bits/stdc++.h>
#include "ricehub.h"
#define LL long long
using namespace std;
int besthub(int R , int L , int X[] , LL B){
   vector<LL> p(R);
   for(int i = 0;i < R;i ++){
      if(i > 0){
         p[i] = p[i - 1];
      }
      p[i] += X[i];
   }
   auto range_sum = [&](int l , int r){
      if(l > r){
         return 0LL;
      }
      return p[r] - (l > 0 ? p[l - 1] : 0);
   };
   int ans = 0;
   for(int i = 0;i < R;i ++){
      int ll , rr;
      LL t = 0 , S = 0;
      for(int bit = 30;bit >= 0;bit --){
         t += 1 << bit;
         int l = i , r = i;
         for(int BIT = 20;BIT >= 0;BIT --){
            l -= 1 << BIT;
            if(l < 0 || X[l] < X[i] - t){
               l += 1 << BIT;
            }
            r += 1 << BIT;
            if(r >= R || X[r] > X[i] + t){
               r -= 1 << BIT;
            }
         }
         LL sL = (i - l) * X[i] - range_sum(l , i - 1);
         LL sR = range_sum(i + 1 , r) - (r - i) * X[i];
         if(sL + sR > B){
            t -= 1 << bit;
         }else{
            ll = l;
            rr = r;
            S = sL + sR;
         }
      }
      int old_l = ll , old_r = rr;
      ans = max(ans , rr - ll + 1);
      for(int bit = 20;bit >= 0;bit --){
         rr += 1 << bit;
         if(rr >= R){
            rr -= 1 << bit;
         }else{
            LL E = range_sum(old_r + 1 , rr) - (rr - old_r) * X[i];
            if(S + E > B){
               rr -= 1 << bit;
            }else{
               ans = max(ans , rr - old_l + 1);
            }
         }
         ll -= 1 << bit;
         if(ll < 0){
            ll += 1 << bit;
         }else{
            LL E = (old_l - ll) * X[i] - range_sum(ll , old_l - 1);
            if(S + E > B){
               ll += 1 << bit;
            }else{
               ans = max(ans , old_r - ll + 1);
            }
         }
      }
   }
   return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32