結果
問題 | No.798 コレクション |
ユーザー | Tiramister |
提出日時 | 2019-03-15 22:04:21 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,339 bytes |
コンパイル時間 | 1,257 ms |
コンパイル使用メモリ | 119,804 KB |
実行使用メモリ | 4,504 KB |
最終ジャッジ日時 | 2023-09-14 13:37:13 |
合計ジャッジ時間 | 3,688 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 2 ms
4,376 KB |
testcase_24 | AC | 125 ms
4,376 KB |
testcase_25 | AC | 126 ms
4,380 KB |
ソースコード
// IO library #include <cstdio> #include <iomanip> #include <ios> #include <iostream> // algorithm library #include <algorithm> #include <cmath> #include <numeric> #include <random> // contancer library #include <bitset> #include <deque> #include <map> #include <queue> #include <set> #include <string> #include <tuple> #include <vector> using namespace std; using ll = long long; using ld = long double; template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p); template <class T> ostream& operator<<(ostream& os, vector<T> v) { os << "["; for (auto vv : v) os << vv << ","; return os << "]"; } template <class T> ostream& operator<<(ostream& os, set<T> v) { os << "{"; for (auto vv : v) os << vv << ","; return os << "}"; } template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.first << "," << p.second << ")"; } template <class K, class T> ostream& operator<<(ostream& os, map<K, T> v) { os << "{"; for (auto vv : v) os << vv << ","; return os << "}"; } template <class T> ostream& operator<<(ostream& os, queue<T> q) { os << "["; while (!q.empty()) { os << q.front() << ","; q.pop(); } return os << "]"; } template <class T> ostream& operator<<(ostream& os, priority_queue<T> q) { os << "{"; while (!q.empty()) { os << q.top() << ","; q.pop(); } return os << "}"; } const ll MOD = 1000000007; // const ll MOD = 998244353; // const int INF = 1 << 25; const ll INF = 1LL << 50; // const ld PI = acos(-1); // const ld EPS = 1e-10; // mt19937 mt(ll(time(0))); template <class T> vector<T> Vec(size_t l, T v) { return vector<T>(l, v); } template <class T, class... Ts> auto Vec(size_t l, Ts... ts) { return vector<decltype(Vec<T>(ts...))>(l, Vec<T>(ts...)); } template <typename T> inline T sq(T a) { return a * a; } template <typename T> inline T iceil(T n, T d) { return (n + d - 1) / d; } template <typename T> T gcd(T a, T b) { while (b > 0) { a %= b; swap(a, b); } return a; } template <typename T, typename U> T ipow(T b, U n) { T ret = 1; while (n > 0) { if (n & 1) ret *= b; n >>= 1; b *= b; } return ret; } template <typename T, typename U> T mpow(T b, U n) { T ret = 1; while (n > 0) { if (n & 1) ret = ret * b % MOD; n >>= 1; b = b * b % MOD; } return ret; } int main() { int N; cin >> N; vector<ll> A(N), B(N); for (int i = 0; i < N; ++i) { cin >> A[i] >> B[i]; } vector<bool> choosed(N, false); for (int t = 0; t < N - N / 3; ++t) { vector<pair<pair<ll, ll>, ll>> val(N); for (int i = 0; i < N; ++i) { val[i].second = i; val[i].first = (choosed[i] ? make_pair(INF, INF) : make_pair(A[i] + B[i] * t, B[i])); } sort(val.begin(), val.end()); choosed[val.front().second] = true; } vector<pair<ll, ll>> buy; for (int i = 0; i < N; ++i) { if (!choosed[i]) continue; buy.push_back(make_pair(B[i], A[i])); } sort(buy.rbegin(), buy.rend()); ll ans = 0; for (int d = 0; d < buy.size(); ++d) { ans += buy[d].second + buy[d].first * d; } cout << ans << endl; return 0; }