(200720) 코드포스

Codeforces materials usage license (v. 0.1) 에 따라 codeforces.com 의 문제임을 알립니다.

Original problem link: Problem - 1379C - Codeforces


Example

Input

2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1

Output

14
16


Common codes for Codeforces
#include <algorithm>
#include <array>
#include <cmath>
#include <functional> 
#include <iostream>
#include <memory>
#include <queue>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>

namespace predefined {

#ifdef CODEFORCES_DEBUG
  constexpr bool kIsDebug = true;
#else
  constexpr bool kIsDebug = false;
#endif

enum class LogType {
  INFO,
  DEBUG
};

template <LogType Type, bool... Bools>
struct Log;

template <>
struct Log<LogType::INFO> {
  Log() {}
  ~Log() { std::cout << '\n'; }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, true>{
  Log() {}
  ~Log() { std::cout << '\n'; }

  void Open() {
    freopen("input.txt", "r", stdin);
  }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, false> {
  Log() {}
  ~Log() {}

  void Open() {}

  template <typename T>
  Log& operator<< (const T &t) { return *this; }
};

namespace solver {

using SolveFunc = std::function<void()>;

template<typename MultiRunner>
void Run(SolveFunc solve_func);

template<>
void Run<std::true_type>(SolveFunc solve_func) {
  int test_case;
  std::cin >> test_case;

  while (test_case--) {
    solve_func();
  }
}

template<>
void Run<std::false_type>(SolveFunc solve_func) {
  solve_func();
}

} // solver

template <bool MultiTest>
struct Solver {
  constexpr static bool condition = MultiTest | kIsDebug;
  typedef typename std::conditional<condition, std::true_type, std::false_type>::type run_type;

  explicit Solver(solver::SolveFunc solve_func) {
    solver::Run<run_type>(solve_func);
  }
};

template<typename T>
struct BoolMap {
  explicit BoolMap(const T &_true_value, const T &_false_value) 
    : true_value(_true_value),
      false_value(_false_value) {}

  const T true_value;
  const T false_value;

  const T inline GetValue(const bool bool_key) const {
    return bool_key ? true_value : false_value;  
  };
};

}  // predefined;

#define LOG_INFO predefined::Log<predefined::LogType::INFO>()
#define LOG_DEBUG predefined::Log<predefined::LogType::DEBUG, predefined::kIsDebug>()
#define LOG(LEVEL) LOG_##LEVEL
#define LABEL(variable_name) #variable_name << ": " << variable_name << " "

#define INIT_ANSWER(type, true_value, false_value) \
  const predefined::BoolMap<type> predefined_bool_map(true_value, false_value)
#define INIT_STRING_ANSWER(true_string, false_string) \
  INIT_ANSWER(std::string, true_string, false_string)
#define GET_ANSWER(bool_key) \
  predefined_bool_map.GetValue(bool_key)

#define INIT_CODEFORCES() \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(NULL); \
  LOG(DEBUG).Open();

1379C 오답
namespace {
using namespace std;

constexpr bool kMultiTestCase = true;
using Solver = predefined::Solver<kMultiTestCase>;

}  // unnamed namespace;

void solve() {
  int64_t n, m;
  cin >> n >> m;

  vector<pair<bool, pair<int64_t, int64_t>>> flowers(m);
  for (int i = 0; i < m; ++i) {
    cin >> flowers[i].second.first >> flowers[i].second.second;
    flowers[i].first = false;
  }

  sort(flowers.begin(), flowers.end(),
       [](const pair<bool, pair<int64_t, int64_t>> &a,
          const pair<bool, pair<int64_t, int64_t>> &b)->bool{
    return a.second.first > b.second.first;
  });

  int64_t max_value = 0;
  int max_index = -1;
  for (int i = 0; i < flowers.size(); ++i) {
    if (max_value < flowers[i].second.second) {
      max_value = flowers[i].second.second;
      max_index = i;
    } else if (max_value == flowers[i].second.second && 
               (max_index == -1 || flowers[max_index].second.first < flowers[i].second.first)) {
      max_value = flowers[i].second.second;
      max_index = i;
    }
  }

  int64_t ans = 0;
  int64_t sum = 0;
  int64_t partial_max = 0;
  for (int i = 0; i < flowers.size(); ++i) {
    --n;
    sum += flowers[i].second.first;
    flowers[i].first = true;
    if (partial_max < flowers[i].second.second) partial_max = flowers[i].second.second;
    ans = max(ans, sum + partial_max * n);

    if (flowers[max_index].first == false) {
      int64_t add = 0;
      if (n >= 1) {
        add += flowers[max_index].second.first + flowers[max_index].second.second * (n - 1);
      }
      ans = max(ans, sum + add);
    } else {
      int64_t add = flowers[max_index].second.second * n;
      ans = max(ans, sum + add);
    }
  }
  
  LOG_INFO << ans;

  return;
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver(std::bind(&solve));

  return 0;
}