Submission #297172

#	Time	Username	Problem	Language	Result	Execution time	Memory
297172		Kastanda	Rice Hub (IOI11_ricehub)	C++11	100 / 100	19 ms	2944 KiB

ricehub

/*
    Take me to church
    I'll worship like a dog at the shrine of your lies
    I'll tell you my sins and you can sharpen your knife
    Offer me that deathless death
    Good God, let me give you my life
*/
#include<bits/stdc++.h>
#include "ricehub.h"
using namespace std;
typedef long long ll;
const int N = 100005;
int n, L, A[N];
ll B, P[N];
inline bool SolveOdd(int md)
{
    md >>= 1;
    for (int i = md + 1; i + md <= n; i ++)
        if (P[i + md] + P[i - 1 - md] - P[i] - P[i - 1] <= B)
            return (1);
    return (0);
}
inline bool SolveEven(int md)
{
    md >>= 1; md --;
    for (int i = md + 1; i + md + 1 <= n; i ++)
        if (P[i + md + 1] + P[i - 1 - md] - P[i] - P[i - 1] <= B + A[i])
            return (1);
    return (0);
}
inline bool Solve(int md)
{
    if (md & 1)
        return (SolveOdd(md));
    return (SolveEven(md));
}
int besthub(int _n, int _L, int * _A, ll _B)
{
    n = _n; L = _L; B = _B;
    for (int i = 1; i <= n; i ++)
        A[i] = _A[i - 1], P[i] = P[i - 1] + A[i];
    int le = 1, ri = n + 1, md;
    while (ri - le > 1)
    {
        md = (le + ri) >> 1;
        if (Solve(md))
            le = md;
        else
            ri = md;
    }
    return (le);
}

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