oj.uz

Submission #228335

# Submission time Handle Problem Language Result Execution time Memory
228335 2020-04-30T15:10:47 Z quocnguyen1012 Hacker (BOI15_hac) C++14
0 / 100
 5 ms 384 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 / 2 + 2; ++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
0 / 20.0

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

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 -