oj.uz

Submission #873861

# Submission time Handle Problem Language Result Execution time Memory
873861 2023-11-16T01:56:40 Z 1075508020060209tc Hacker (BOI15_hac) C++14
20 / 100
 99 ms 24404 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ar[1000006];
int ps[1000006];
int pok[1000006];

int ok(int mi){
for(int i=1;i<=n+n;i++){
    pok[i]=0;
}
int len=(n+1)/2;
for(int i=len;i<=n+n;i++){
    pok[i]=0;
    if(ps[i]-ps[i-len]>=mi){
        pok[i]=1;
    }
}
for(int i=1;i<=n+n;i++){
    pok[i]+=pok[i-1];
}
for(int i=len;i<=n+n;i++){
    if(pok[i]-pok[i-len]==len){
        return 1;
    }
}
return 0;
}
int br[1000006];

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
        ar[i+n]=ar[i];
    }
    for(int i=1;i<=n+n;i++){
        ps[i]=ar[i]+ps[i-1];
    }
    int len=(n+1)/2;
    for(int i=len;i<=n+n;i++){
        br[i]=ps[i]-ps[i-len];
    }
    deque<int>dq;
    for(int i=len;i<=len+len-1;i++){
        while(dq.size()&&br[dq.front()]>=br[i]){dq.pop_front();}
        dq.push_front(i);
    }
    int ans=br[dq.back()];
    for(int i=len+len;i<=n+n;i++){
        while(dq.size()&&br[dq.front()]>=br[i]){dq.pop_front();}
        dq.push_front(i);
        ans=max(ans,br[dq.back()]);
        if(dq.back()==i-len+1){dq.pop_back(); }
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 16 ms 7364 KB Output is correct
5 Correct 36 ms 13684 KB Output is correct
6 Correct 52 ms 15700 KB Output is correct
7 Correct 59 ms 17580 KB Output is correct
8 Correct 99 ms 24404 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -