oj.uz

Submission #232615

# Submission time Handle Problem Language Result Execution time Memory
232615 2020-05-17T16:24:48 Z AlexLuchianov Candies (JOI18_candies) C++14
8 / 100
 94 ms 25464 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <set>

using namespace std;

using ll = long long;
int const nmax = 100000;
ll v[1 + nmax];

set<int> myset;
set<pair<ll,int>> pq;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  ll result = 0;
  for(int i = 1;i <= n; i++){
    cin >> v[i];
    myset.insert(i);
    pq.insert({v[i], i});
  }
  int lim = (n + 1) / 2;

  for(int i = 1;i <= lim; i++){
    set<pair<ll, int>>::iterator itpq = pq.end();
    itpq--;

    result += itpq->first;
    cout << result << '\n';
    int id = itpq->second;
    pq.erase(itpq);

    set<int>::iterator it, it2;
    myset.erase(id);
    it = myset.lower_bound(id);

    if(it == myset.end()){
      if(0 < myset.size()) {
        it--;
        pq.erase({v[*it], *it});
        myset.erase(it);
      }
      continue;
    }
    if(it == myset.begin()){
      pq.erase({v[*it], *it});
      myset.erase(it);
      continue;
    }
    it2 = it;
    it2--;

    v[id] = v[*it2] + v[*it] - v[id];
    pq.erase({v[*it2], *it2});
    pq.erase({v[*it], *it});
    pq.insert({v[id], id});

    myset.erase(it);
    myset.erase(it2);
    myset.insert(id);
  }
  cout << '\n';
  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 6 ms 640 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 6 ms 640 KB Output is correct
16 Correct 6 ms 640 KB Output is correct
17 Correct 6 ms 640 KB Output is correct
18 Correct 7 ms 640 KB Output is correct
19 Correct 6 ms 640 KB Output is correct
20 Correct 7 ms 640 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 6 ms 640 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 6 ms 640 KB Output is correct
16 Correct 6 ms 640 KB Output is correct
17 Correct 6 ms 640 KB Output is correct
18 Correct 7 ms 640 KB Output is correct
19 Correct 6 ms 640 KB Output is correct
20 Correct 7 ms 640 KB Output is correct
21 Runtime error 94 ms 25464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -