oj.uz

Submission #239560

# Submission time Handle Problem Language Result Execution time Memory
239560 2020-06-16T10:44:14 Z gratus907 Rice Hub (IOI11_ricehub) C++17
0 / 100
 51 ms 3408 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

long long _X[101010], _R;
long long presum[101010];
long long curbest = 0, curans = 0;
inline long long range_sum(int Left, int Right, int Target)
{
    if (Left <= 0 || Right<=0 || Right>_R || Left>_R) return LLONG_MAX;
    int tmp = presum[Right]-presum[Left-1];
    return abs(tmp - _X[Target]*(Right-Left+1));
}
int besthub(int R, int L, int X[], long long B)
{
    _R = R;
    for (int i = 1; i<=R; i++)
    {
        _X[i] = X[i];
        presum[i] = presum[i-1]+X[i];
    }
    for (int i = 1; i<=R; i++)
    {
        int lo = 0, hi = min(i-1,R-i)+1;
        while(lo+1 < hi)
        {
            int d = (lo+hi)/2;
            long long lsum = range_sum(i-d, i-1, i);
            long long rsum = range_sum(i+1, i+d, i);
            if (lsum+rsum <= B)
                lo = d;
            else 
                hi = d;
        }
        long long possible_gets = 2*lo+1;
        if (possible_gets>=curbest)
        {
            curbest = possible_gets;
            curans = i;
        }
    }

    for (int i = 1; i<R; i++)
    {
        int len = X[i+1]-X[i];
        if (len > B) continue;
        int lo = 0, hi = min(i-1,R-i-1)+1;
        while(lo+1 < hi)
        {
            int d = (lo+hi)/2;
            long long lsum = range_sum(i-d, i-1, i);
            long long rsum = range_sum(i+2, i+d+1, i);
            if (lsum+rsum+len <= B)
                lo = d;
            else 
                hi = d;
        }
        long long possible_gets = 2*lo+2;
        if (possible_gets>=curbest)
        {
            curbest = possible_gets;
            curans = i;
        }
    }
    return curbest;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 896 KB Output is correct
2 Correct 11 ms 896 KB Output is correct
3 Correct 41 ms 3328 KB Output is correct
4 Incorrect 51 ms 3408 KB Output isn't correct
5 Halted 0 ms 0 KB -