Submission #318336

#	Time	Username	Problem	Language	Result	Execution time	Memory
318336		AlexLuchianov	Coins (BOI06_coins)	C++14	90 / 100	440 ms	10852 KiB

coins

#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;
      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[v[i][0] - 1] = std::max(mp[v[i][0] - 1], acc);
        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 (stderr)

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: 90 / 100