oj.uz

Submission #318337

# Submission time Handle Problem Language Result Execution time Memory
318337 2020-11-01T10:03:51 Z AlexLuchianov Coins (BOI06_coins) C++14
100 / 100
 434 ms 5348 KB 
#include <iostream>
#include <vector>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 500000;
int v[1 + nmax][2];

std::map<int,std::pair<int,int>> mp; 

int main() {
  int n, k;
  std::cin >> n >> k;
  for(int i = 1;i <= n; i++) {
    int c, k;
    std::cin >> v[i][0] >> v[i][1];
  }
  mp[k - 1] = {0, 0};
  for(int i = n; 1 <= i; i--) {
    std::map<int, std::pair<int,int>>::iterator it = mp.end();
    it--;
    while(0 < mp.size() && v[i][0] <= it->first) {
      int rest = it->first;
      std::pair<int, int> acc = it->second;
      mp[v[i][0] - 1] = std::max(mp[v[i][0] - 1], acc);
      if(v[i][0] * 2 - 1 <= rest) 
        mp[v[i][0] - 1] = std::max(mp[v[i][0] - 1], {acc.first + !v[i][1], acc.second - v[i][0]});
      else {
        mp[rest - v[i][0]] = std::max(mp[rest - v[i][0]], {acc.first + !v[i][1], acc.second - v[i][0]}); 
      }
      mp.erase(it--);
    }
  }
  std::pair<int,int> result;
  for(std::map<int, std::pair<int,int>>::iterator it = mp.begin(); it != mp.end(); it++)
    result = std::max(result, it->second);
  if(0 < result.first)
    std::cout << result.first << '\n' << k + result.second;
  else
    std::cout << 0 << '\n' << k - 1 << '\n';
  return 0;
}

Compilation message

coins.cpp: In function 'int main()':
coins.cpp:22:9: warning: unused variable 'c' [-Wunused-variable]
   22 |     int c, k;
      |         ^
coins.cpp:22:12: warning: unused variable 'k' [-Wunused-variable]
   22 |     int c, k;
      |            ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 331 ms 4240 KB Output is correct
8 Correct 336 ms 4196 KB Output is correct
9 Correct 434 ms 5092 KB Output is correct
10 Correct 422 ms 5348 KB Output is correct