Submission #1027101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027101		kkkkkkkk	Rice Hub (IOI11_ricehub)	C++14	100 / 100	13 ms	4196 KiB

ricehub

#include <bits/stdc++.h>

using namespace std;

vector<int> v;
long long B;
long long pref_sum[100005];

bool proveri(int k) {
    for (int i=0;i<=v.size()-k;i++) {
        int poz=(i+i+k)/2;
        int hub=v[poz];
        long long zbir_levo=hub*(poz-i)-(pref_sum[poz]-pref_sum[i]+v[i]-v[poz]);
        long long zbir_desno=(pref_sum[i+k-1]-pref_sum[poz]+v[poz])-hub*(i+k-poz);
        if (zbir_levo+zbir_desno<=B) return true;
    }
    return false;
}

int besthub(int R, int L, int a[], long long b) {
    B=b;
    for (int i=0;i<R;i++)
        v.push_back(a[i]);
    pref_sum[0]=a[0];
    for (int i=1;i<R;i++)
        pref_sum[i]=pref_sum[i-1]+a[i];
    int l=1, r=R+1;
    while (l+1<r) {
        int mid=(l+r)/2;
        if (proveri(mid)) l=mid;
        else r=mid;
    }
    return l;
}

Compilation message (stderr)

ricehub.cpp: In function 'bool proveri(int)':
ricehub.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i=0;i<=v.size()-k;i++) {
      |                  ~^~~~~~~~~~~~

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