oj.uz

답안 #879272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879272 2023-11-27T05:07:45 Z NeroZein Candies (JOI18_candies) C++17
0 / 100
 1 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}); 
  }
  L[N + 1] = R[N + 1] = N + 1;
  Set.insert({LLONG_MAX / 10, 0, 0}); 
  Set.insert({LLONG_MAX / 10, N + 1, N + 1}); 
  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]; 
    Set.erase({-Val[newL], newL, l - 1});      
    Set.erase({-Val[r + 1], r + 1, newR});      
    long long newVal = Val[newL] + Val[r + 1] + val; 
    L[newR] = newL;
    R[newL] = newR;
    Val[newL] = newVal; 
    Set.insert({-newVal, newL, newR}); 
    cout << ans << '\n'; 
  }
  return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 92.0

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