Submission #153907

#	Time	Username	Problem	Language	Result	Execution time	Memory
153907		arnold518	도넛 (JOI14_ho_t3)	C++14	100 / 100	241 ms	4004 KiB

2014_ho_t3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N;
ll A[MAXN+10], S;

bool decide(ll x)
{
    int i, j;

    int pa=0, pb=N-1;
    ll suma=0, sumb=0;

    vector<ll> SA(N), SB(N);
    for(i=0; i<N; i++)
    {
        for(; suma<x; pa=(pa+1)%N) suma+=A[pa];
        SA[i]=suma;
        suma-=A[i];
    }
    for(i=N-1; i>=0; i--)
    {
        for(; sumb<x; pb=(pb+N-1)%N) sumb+=A[pb];
        SB[i]=sumb;
        sumb-=A[i];
    }
    for(i=0; i<N; i++) if(S-SA[i]-SB[(i+N-1)%N]>=x) return true;
    return false;
}

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=0; i<N; i++) scanf("%lld", &A[i]), S+=A[i];

    ll lo=0, hi=S;
    while(lo+1<hi)
    {
        ll mid=lo+hi>>1;
        if(decide(mid)) lo=mid;
        else hi=mid;
    }
    printf("%lld", lo);
}

Compilation message (stderr)

2014_ho_t3.cpp: In function 'bool decide(ll)':
2014_ho_t3.cpp:15:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
2014_ho_t3.cpp: In function 'int main()':
2014_ho_t3.cpp:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mid=lo+hi>>1;
                ~~^~~
2014_ho_t3.cpp:39:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
2014_ho_t3.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
2014_ho_t3.cpp:42:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=0; i<N; i++) scanf("%lld", &A[i]), S+=A[i];
                        ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50