Submission #799618

#	Time	Username	Problem	Language	Result	Execution time	Memory
799618		Liudas	Rice Hub (IOI11_ricehub)	C++17	100 / 100	13 ms	4248 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
int besthub(int N, int L, int arr[], long long B){
    vector<long long> brr;
    for(int i = 0; i < N; i ++){
        brr.push_back(arr[i]);
    }
    long long ss = 0, ee = 1e9;
    vector <long long> suf(N + 1), pref(N + 1);
    for(int i = 0; i < N; i ++){
        pref[i+1] = pref[i]+1ll*brr[i];
        suf[N-i-1] = 1ll * suf[N-i]+brr[N-i-1] ;
    }
    int l = 1, r = N + 1;
    while(l + 1 < r){
        int mid = (l + r + 1) / 2;
        int best = 0;
        //cout << "start " << mid << endl;
        for(int i = 0; i < N - mid + 1; i ++){
            long long t = i + mid/ 2, tt = arr[t];
            long long s = suf[i] - suf[t];
            long long p = pref[i + mid] - pref[t];
            long long price = tt * (t - i) - s + p - tt * (i + mid - t);
            if(price <= B){
                best = mid;
                break;
            }
        }
        //cout <<"ans " << best <<  " " << mid << endl;
        if(best == mid){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    return l;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:9:15: warning: unused variable 'ss' [-Wunused-variable]
    9 |     long long ss = 0, ee = 1e9;
      |               ^~
ricehub.cpp:9:23: warning: unused variable 'ee' [-Wunused-variable]
    9 |     long long ss = 0, ee = 1e9;
      |                       ^~

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