Submission #43769

#	Time	Username	Problem	Language	Result	Execution time	Memory
43769		PowerOfNinjaGo	Hacker (BOI15_hac)	C++14	100 / 100	96 ms	32504 KiB

hac

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 5e5+5;
int arr[2*maxn];
int qs[2*maxn];
int s[2*maxn];
int main()
{
    //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
    int n; scanf("%d", &n);
    for(int i = 1; i<= n; i++) scanf("%d", arr+i);
    for(int i = 1; i<= n; i++) arr[n+i] = arr[i];
    for(int i = 1; i<= 2*n; i++) qs[i] = qs[i-1]+arr[i];
    int k = n/2;
    for(int i = 1; i+k-1<= 2*n; i++) s[i] = qs[i+k-1]-qs[i-1];
    int best = 2e9;
    deque< ii > dq;
    for(int i = 2; i< n-k+1; i++)
    {
        while(!dq.empty() && dq.back().X<= s[i]) dq.pop_back();
        dq.push_back(ii(s[i], i));
    }
    for(int i = 1; i<= n; i++)
    {
        while(!dq.empty() && dq.back().X<= s[n-k+i]) dq.pop_back();
        dq.push_back(ii(s[n-k+i], n-k+i));
        while(!dq.empty() && dq.front().Y<= i) dq.pop_front();
        best = min(best, dq.front().X);
    }
    printf("%d\n", qs[n]-best);
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:18:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf("%d", &n);
                           ^
hac.cpp:19:50: 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("%d", arr+i);
                                                  ^

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