Submission #226371

#	Time	Username	Problem	Language	Result	Execution time	Memory
226371		MKopchev	Hacker (BOI15_hac)	C++14	100 / 100	260 ms	8800 KiB

hac

#include<bits/stdc++.h>
using namespace std;
const int nmax=5e5+42;
int n,inp[nmax];

long long pref[nmax];

int take;

long long ask(int l,int r)
{
    while(l>n)l=l-n;
    while(r>n)r=r-n;

    if(l<=r)return pref[r]-pref[l-1];
    return pref[r]+pref[n]-pref[l-1];
}
bool can(long long want)
{
    int now=0;
    for(int i=1;i<=2*n;i++)
    {

        if(ask(i,i+take-1)>=want)now++;
        else now=0;


        if(now>=take)
        {

            return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    take=(n+1)/2;

    for(int i=1;i<=n;i++)pref[i]=pref[i-1]+inp[i];

    long long ok=0,not_ok=1e18;

    while(not_ok-ok>1)
    {
        long long av=(ok+not_ok)/2;
        if(can(av))ok=av;
        else not_ok=av;
    }

    printf("%lld\n",ok);
    return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
hac.cpp:39:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40