oj.uz

답안 #879250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879250 2023-11-27T04:04:51 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 = max(1, L[l - 1]);
    int newR = min(N, R[r + 1]); 
    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});      
    }
    Set.insert({-newVal, newL, newR}); 
    L[newR] = newL;
    R[newL] = newR;
    Val[newL] = newVal; 
    cout << ans << '\n'; 
  }
  return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -