Submission #798186

#	Time	Username	Problem	Language	Result	Execution time	Memory
798186		fuad27	Candies (JOI18_candies)	C++17	0 / 100	2 ms	596 KiB

candies

#include<bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
using namespace std;
void solve() {
  int n;
  cin >> n;
  long long a[n];
  set<pair<long long,long long>> s, s1;
  for(int i = 0;i<n;i++){
    cin >> a[i];
    s.insert({a[i], i});
    s1.insert({i, a[i]});
  }
  long long sum=0;
  for(int i = 1;i<=(n+1)/2;i++) {
//    for(auto j:s)cout << j.first << " " << j.second << "\n";
//    cout <<"\n";
    long long mx;
    int idx;
    mx=(*(--s.end())).first;
    idx=(*(--s.end())).second;
    sum+=mx;
    s.erase({mx, idx});
    s1.erase({idx, mx});
    auto it1=s1.lower_bound({idx+1, 0});
    auto it2=it1;
    if(s.size()) {
      if(it1==s1.end() or it1==s1.begin()) {
        if(it1==s1.end())--it1;
        int val=(*it1).second;
        s.erase({(*it1).second, (*it1).first});
        s1.erase(it1);
        s.insert({val-mx, idx});
        s1.insert({idx,val-mx});
      }
      else {
        it2--;
        long long sm=(*it1).second+(*it2).second-mx;
        s.erase({(*it2).second, (*it2).first});
        s1.erase(it2);
        s.erase({(*it1).second, (*it1).first});
        s1.erase(it1);
        s.insert({sm, idx});
        s1.insert({idx, sm});
      }
    }
    cout << sum << "\n";
  }
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int t=1;
  while(t--)solve();
  return 0;
}

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