oj.uz

Submission #879274

# Submission time Handle Problem Language Result Execution time Memory
879274 2023-11-27T05:14:31 Z NeroZein Candies (JOI18_candies) C++17
0 / 100
 2 ms 2652 KB 
#include "bits/stdc++.h"
using namespace std;
 
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
 
const int MAX_N = 2e5 + 5; 
 
int A[MAX_N]; 
int L[MAX_N], R[MAX_N]; 
long long Val[MAX_N];
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  for (int i = 1; i <= N; ++i) {
    cin >> A[i]; 
  }
  set<array<long long, 3>> Set; 
  for (int i = 1; i <= N; ++i) {
    L[i] = R[i] = i;
    Val[i] = A[i]; 
    Set.insert({-A[i], i, i}); 
  }
  long long ans = 0; 
  for (int i = 1; i <= (N + 1) / 2; ++i) {
    auto [val, l, r] = *Set.begin(); 
    Set.erase({val, l, r}); 
    ans += -val; 
    int newL = L[l - 1];
    int newR = R[r + 1]; 
    //deb(l) deb(r) deb(newL) deb(newR) cout << '\n';
    long long newVal = Val[L[l - 1]] + Val[r + 1] + val; 
    if (L[l - 1]) {
      int tl = L[l - 1]; 
      Set.erase({-Val[tl], tl, l - 1});      
    }
    if (R[r + 1]) {
      int tr = R[r + 1]; 
      Set.erase({-Val[r + 1], r + 1, tr});      
    }
    if (newL && newR) {
      Set.insert({-newVal, newL, newR});       
    }
    L[newR] = newL;
    R[newL] = newR;
    Val[newL] = newVal; 
    //deb(Set) cout << '\n';
    cout << ans << '\n'; 
  }
  return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2528 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Incorrect 2 ms 2652 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2528 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Incorrect 2 ms 2652 KB Output isn't correct
8 Halted 0 ms 0 KB -