Submission #1326386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326386		horiaboeriu	Rice Hub (IOI11_ricehub)	C++20	100 / 100	8 ms	1848 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
const int MAXN = 100000;
int v[MAXN + 1];
long long sp[MAXN + 1];
long long getSum(int st, int dr) {
    return sp[dr] - sp[st - 1];
}
long long calc(int st, int dr) {
    int mij;
    mij = (st + dr) / 2;//il pun in median, adica in v[mij]
    return (long long)v[mij] * (mij - st + 1) - getSum(st, mij) + getSum(mij + 1, dr) - (long long)v[mij] * (dr - mij);
}
int besthub(int n, int L, int X[], long long b) {
    //o sa aleg o subsecventa ca pozitiile sa fie cat mai apropiate
    //si o sa pun rice hubul in median ca sa aiba distanta minima pana la toate
    //si fac 2 pointers ca sa extind subsecventa
    //O(n)
    int i, j, rez;
    for (i = 1; i <= n; i++) {
        v[i] = X[i - 1];
        sp[i] = sp[i - 1] + v[i];
    }
    j = 1;
    rez = 0;
    for (i = 1; i <= n; i++) {
        while (j <= n && calc(i, j) <= b) {
            j++;
        }
        if (j - i > rez) {
            rez = j - i;
        }
    }
    return rez;
}

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