Submission #440641

# Submission time Handle Problem Language Result Execution time Memory
440641 2021-07-02T15:22:26 Z peijar Candies (JOI18_candies) C++17
100 / 100
709 ms 30412 KB
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbElem;
  cin >> nbElem;

  vector<int> val(nbElem);
  for (auto &v : val)
    cin >> v;

  set<pair<int, int>> choices, revChoices;
  for (int iEl = 0; iEl < nbElem; ++iEl) {
    choices.emplace(val[iEl], iEl);
    revChoices.emplace(iEl, val[iEl]);
  }
  choices.emplace(-1e18, -1);
  choices.emplace(-1e18, nbElem);
  revChoices.emplace(-1, -1e18);
  revChoices.emplace(nbElem, -1e18);

  int curRet = 0;
  for (int prend = 1; prend <= (nbElem + 1) / 2; ++prend) {
    auto [gain, pos] = *choices.rbegin();
    curRet += gain;
    cout << curRet << '\n';
    if (prend + 1 > (nbElem + 1) / 2)
      break;

    choices.erase({gain, pos});
    revChoices.erase({pos, gain});
    auto it = revChoices.lower_bound({pos, -(int)1e18});
    int gainNext = -gain;
    if (it != revChoices.end()) {
      gainNext += it->second;
      choices.erase({it->second, it->first});
      revChoices.erase(it);
    }
    it = revChoices.lower_bound({pos, -(int)1e18});
    if (it != revChoices.begin()) {
      it--;
      gainNext += it->second;
      choices.erase({it->second, it->first});
      revChoices.erase(it);
    }
    choices.emplace(gainNext, pos);
    revChoices.emplace(pos, gainNext);
  }
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 3 ms 584 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 3 ms 608 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 3 ms 584 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 3 ms 584 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 3 ms 608 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 3 ms 584 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 709 ms 30336 KB Output is correct
22 Correct 683 ms 30276 KB Output is correct
23 Correct 639 ms 30288 KB Output is correct
24 Correct 352 ms 30176 KB Output is correct
25 Correct 329 ms 30148 KB Output is correct
26 Correct 310 ms 30140 KB Output is correct
27 Correct 320 ms 30408 KB Output is correct
28 Correct 341 ms 30412 KB Output is correct
29 Correct 311 ms 30348 KB Output is correct
30 Correct 337 ms 30372 KB Output is correct
31 Correct 354 ms 30276 KB Output is correct
32 Correct 309 ms 30268 KB Output is correct
33 Correct 480 ms 30024 KB Output is correct
34 Correct 438 ms 30028 KB Output is correct
35 Correct 461 ms 30096 KB Output is correct
36 Correct 686 ms 30240 KB Output is correct
37 Correct 695 ms 30280 KB Output is correct
38 Correct 683 ms 30288 KB Output is correct
39 Correct 299 ms 30084 KB Output is correct
40 Correct 313 ms 30084 KB Output is correct
41 Correct 308 ms 30148 KB Output is correct
42 Correct 326 ms 30296 KB Output is correct
43 Correct 317 ms 30404 KB Output is correct
44 Correct 321 ms 30268 KB Output is correct
45 Correct 335 ms 30300 KB Output is correct
46 Correct 321 ms 30292 KB Output is correct
47 Correct 314 ms 30400 KB Output is correct
48 Correct 451 ms 30132 KB Output is correct
49 Correct 477 ms 30148 KB Output is correct
50 Correct 497 ms 30140 KB Output is correct