Submission #499573

#	Time	Username	Problem	Language	Result	Execution time	Memory
499573		aryan12	Rice Hub (IOI11_ricehub)	C++17	100 / 100	13 ms	2504 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

int besthub(int rice, int len, int a[], long long b) {
    long long pref[rice], suf[rice];
    pref[0] = a[0];
    for(long long i = 1; i < rice; i++) {
      pref[i] = pref[i - 1] + a[i];
    }
    long long right = 0, ans = 0;
    for(long long left = 0; left < rice; left++) {
      right = max(right, left);
      while(right != rice) {
        long long mid = (left + right) / 2;
        long long cur_ans;
        if(left != 0) cur_ans = a[mid] * (mid - left + 1) - pref[mid] + pref[left - 1];
        else cur_ans = a[mid] * (mid - left + 1) - pref[mid];
        if(mid != 0) cur_ans += pref[right] - pref[mid - 1] - a[mid] * (right - mid + 1);
        else cur_ans += pref[right] - a[mid] * (right - mid + 1);
        //cout << "l = " << left << ", mid = " << mid << ", right = " << right << ", cur_ans = " << cur_ans << "\n";
        if(cur_ans <= b) {
          ans = max(ans, right - left + 1);
        }
        else {
          break;
        }
        right++;
      }
    }
    return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:6:27: warning: unused variable 'suf' [-Wunused-variable]
    6 |     long long pref[rice], suf[rice];
      |                           ^~~

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