Submission #739104

#	Time	Username	Problem	Language	Result	Execution time	Memory
739104		Charizard2021	Hacker (BOI15_hac)	C++17	100 / 100	74 ms	10684 KiB

hac

#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std;

int a[500005], n;

int f(int s, int e){
    if(s <= 0){
        return a[e] + (a[n] - a[s+n-1]);
    }
    return a[e] - a[s-1];
}

int px[500005], qx[500005];
deque<int> dq, num;

int main(){
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        a[i] += a[i-1];
    }
    for (int i=1; i<=n; i++) {
        px[i-1] = f(i - (n-1) / 2,i);
    }
    for (int i=0; i<n+(n-1)/2; i++) {
        if(!num.empty() && num.front() == i - (n+1)/2){
            num.pop_front();
            dq.pop_front();
        }
        while (!dq.empty() && dq.back() > px[i%n]) {
            num.pop_back();
            dq.pop_back();
        }
        dq.push_back(px[i%n]);
        num.push_back(i);
        if(i - (n-1)/2 >= 0){
            qx[i - (n-1)/2] = dq.front();
        }
    }
    printf("%d",*max_element(qx,qx+n));
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
hac.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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