Submission #153911

#	Time	Username	Problem	Language	Result	Execution time	Memory
153911		mhy908	도넛 (JOI14_ho_t3)	C++14	100 / 100	161 ms	2940 KiB

2014_ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL arr[200010], ans;
LL f(int stnum, int st, int fin)
{
    if(st==fin)return arr[st]-arr[stnum];
    LL mid=(st+fin)/2+1;
    LL l=arr[mid]-arr[stnum];
    int next=lower_bound(arr+mid+1, arr+stnum+n, l+arr[mid])-arr;
    if(arr[stnum+n]-arr[next]>=l)return f(stnum, mid, fin);
    return f(stnum, st, mid-1);
}
bool ch(int stnum)
{
    LL l=arr[stnum+1]-arr[stnum];
    int next=lower_bound(arr+stnum+2, arr+stnum+n, l+arr[stnum+1])-arr;
    if(arr[stnum+n]-arr[next]>=l)return true;
    return false;
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        LL temp;
        scanf("%lld", &temp);
        arr[i]=arr[i-1]+temp;
    }
    for(int i=1; i<=n; i++)
        arr[i+n]=arr[i]+arr[n];
    for(int i=0; i<n; i++)
        if(ch(i))ans=max(ans, f(i, i+1, i+n-1));
    printf("%lld", ans);
}

Compilation message (stderr)

2014_ho_t3.cpp: In function 'int main()':
2014_ho_t3.cpp:24: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:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &temp);
         ~~~~~^~~~~~~~~~~~~~~

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