Submission #792395

#	Time	Username	Problem	Language	Result	Execution time	Memory
792395		Cookie	Rice Hub (IOI11_ricehub)	C++14	0 / 100	2 ms	852 KiB

ricehub

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 1e5 + 5, mxq = 1e6 + 5, sq = 400;
const int base = (1 << 18);
const int inf = 1e9, neg = -69420;
#include "ricehub.h"
ll a[mxn + 1], pref[mxn + 1], b, n;
bool ck(int mid){
    
    for(int i = 1; i + mid - 1 <= n; i++){
        int id = i + (mid) / 2;
        ll cand = a[id] * (id - i + 1) - pref[id] - pref[i - 1] + pref[i + mid - 1] - pref[id - 1] - (a[id] * (i + mid - 1 - id + 1));
        if(cand <= b)return(1);
        
    }
    return(0);
}
int besthub(int R, int L, int X[], long long B)
{
 b = B; n = R;
  for(int i = 0; i < R; i++)a[i + 1] = X[i];
  for(int i = 1; i <= R; i++){
      pref[i] = pref[i - 1] + a[i];
  }
  int l = 1, r = R, ans = 0;
  while(l <= r){
      int mid = (l + r) >> 1;
      if(ck(mid)){
          ans = mid; l = mid + 1;
      }else{
          r = mid - 1;
      }
  }
  return(ans);
}
/*
#define MAX_R  1000000
static int R, L;
static long long B;
static int X[MAX_R];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

static void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %lld",&R,&L,&B));
  for(i=0; i<R; i++)
    my_assert(1==scanf("%d",&X[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = besthub(R,L,X,B);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect.  Returned %d instead of %d.\n",ans,solution);

  return 0;
}
*/

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