Submission #153908

#	Time	Username	Problem	Language	Result	Execution time	Memory
153908		mhy908	도넛 (JOI14_ho_t3)	C++14	100 / 100	136 ms	2040 KiB

2014_ho_t3

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define llinf 8987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int n;
LL arr[200010], maxx, 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;
    }
    maxx=arr[n];
    for(int i=1; i<=n; i++){
        arr[i+n]=arr[i]+maxx;
    }
    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:32: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:35: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