Submission #218103

#	Time	Username	Problem	Language	Result	Execution time	Memory
218103		extraterrestrial	Candies (JOI18_candies)	C++14	8 / 100	5069 ms	4512 KiB

candies

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

const int N = 2e5 + 10;
int a[N];
bool cur[N];

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }	
  int all = 0;
  for (int i = 1; i <= (n + 1) / 2; i++) {
    pair<int, int> mx = {-1e18, 0};
    for (int j = 1; j <= n; j++) {
      if (!cur[j] && !cur[j - 1] && !cur[j + 1]) {
        mx = max(mx, make_pair(a[j], j));
      }
    }
    pair<int, pair<int, int>> mx2 = {-1e18, {0, 0}};
    int ptr = 1;
    while (ptr <= n) {
      if (!cur[ptr]) {
        ptr++;
        continue;
      }
      int to = ptr;
      while (to + 2 <= n && cur[to + 2]) {
        to += 2;
      }
      if (ptr > 1 && to < n) {
        int sum = 0;
        for (int j = ptr - 1; j <= to + 1; j += 2) {
          sum += a[j];
        }
        for (int j = ptr; j <= to; j += 2) {
          sum -= a[j];
        }
        mx2 = max(mx2, make_pair(sum, make_pair(ptr, to)));
      }
      ptr = to + 2;
    }
    if (mx.F > mx2.F) {
      cur[mx.S] = true;
      all += mx.F;
    }
    else {
      all += mx2.F;
      for (int j = mx2.S.F; j <= mx2.S.S; j += 2) {
        cur[j] = false;
      }
      for (int j = mx2.S.F - 1; j <= mx2.S.S + 1; j += 2) {
        cur[j] = true;
      }
    }
    cout << all << '\n';
  }
} 

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92