Submission #897863

#	Time	Username	Problem	Language	Result	Execution time	Memory
897863		asdasdqwer	Hacker (BOI15_hac)	C++14	100 / 100	53 ms	13836 KiB

hac

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<int> a(n);
    for (int &x:a)cin>>x;

    for (int i=0;i<n;i++) {
        a.push_back(a[i]);
    }

    int windowLength = n/2;
    if (n%2!=0)windowLength++;

    int sm1=0;
    for (int i=0;i<windowLength;i++) {
        sm1+=a[i];
    }

    vector<int> ans(a.size(), 1e9);
    typedef array<int,2> pii;
    deque<pii> dq;
    ans[0]=sm1;
    dq.push_back({sm1, windowLength-1});
    for (int i=1;i<=a.size()-windowLength;i++) {
        int ot = i + windowLength - 1;
        sm1 += a[ot] - a[i-1];

        while (dq.size() && dq.back()[0] >= sm1) dq.pop_back();

        dq.push_back({sm1, ot});

        ans[i] = dq.front()[0];

        if (dq.front()[1] == i) {
            dq.pop_front();
        }
    }

    vector<int> ans2(n);
    for (int i=0;i<n;i++) {
        ans2[i]=ans[i];
        if (i+n<ans.size()) {
            ans2[i]=min(ans2[i], ans[i+n]);
        }
    }

    int mx=0;
    for (int i=0;i<n;i++) {
        mx=max(mx, ans2[i]);
    }

    cout<<mx<<"\n";
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=1;i<=a.size()-windowLength;i++) {
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if (i+n<ans.size()) {
      |             ~~~^~~~~~~~~~~

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