Submission #1124511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124511		fryingduc	Candies (JOI18_candies)	C++20	100 / 100	87 ms	8520 KiB

candies

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

#ifdef duc_debug
#include "D:\\debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n;
long long a[maxn];
int pref[maxn], suf[maxn];
bool mark[maxn];

void solve() {
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    pref[i] = i - 1;
    suf[i] = i + 1;
  }
  a[0] = a[n + 1] = -1e16;
  priority_queue<pair<long long, int>> pq; 
  for(int i = 1; i <= n; ++i) {
    pq.push(make_pair(a[i], i));
  }
  long long res = 0;
  for(int i = 1; i <= (n + 1) / 2; ++i) {
    bool flag = 0;
    while(!pq.empty() and !flag) {
      pair<long long, int> t = pq.top();
      pq.pop();
      if(mark[t.second]) continue;
      flag = 1;
      res += t.first;
      int lst = pref[t.second], nxt = suf[t.second];
      a[t.second] = a[lst] + a[nxt] - a[t.second];
      mark[lst] = mark[nxt] = 1;
      
      pref[t.second] = pref[pref[t.second]];
      suf[t.second] = suf[suf[t.second]];
      
      pref[suf[t.second]] = t.second;
      suf[pref[t.second]] = t.second;
      
      pq.push(make_pair(a[t.second], t.second));
    }    
    cout << res << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();
  return 0;
}

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