oj.uz

Submission #228337

# Submission time Handle Problem Language Result Execution time Memory
228337 2020-04-30T15:12:09 Z quocnguyen1012 Hacker (BOI15_hac) C++14
20 / 100
 76 ms 16072 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array
#define int long long

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 5;

int a[maxn], sum[maxn], N;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int tot = 0;
  cin >> N;
  for(int i = 1; i <= N; ++i){
    cin >> a[i];
    a[i + N] = a[i];
    tot += a[i];
  }
  for(int i = 1; i <= 2 * N; ++i){
    sum[i] = sum[i - 1] + a[i];
  }
  deque<ii> dq;
  for(int i = 1; i <= N - N / 2 + 1; ++i){
    int v = sum[i + N / 2 - 1] - sum[i - 1];
    while(dq.size() && dq.back().fi < v) dq.pop_back();
    dq.eb(v, i);
  }
  int j = N / 2 + 1;
  int res = 0;
  for(int i = 1; i <= N; ++i){
    while(dq.size() && dq.front().se == i) dq.pop_front();
    res = max(res, tot - dq.front().fi);
    ++j;
    int v = sum[j + N / 2 - 1] - sum[j - 1];
    while(dq.size() && dq.back().fi < v) dq.pop_back();
    dq.eb(v, j);
  }
  cout << res;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 488 KB Output is correct
4 Correct 19 ms 2944 KB Output is correct
5 Correct 30 ms 6656 KB Output is correct
6 Correct 41 ms 8192 KB Output is correct
7 Correct 48 ms 9720 KB Output is correct
8 Correct 76 ms 16072 KB Output is correct

Subtask #4
0 / 40.0

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