結果
問題 | No.817 Coin donation |
ユーザー | chocopuu |
提出日時 | 2019-04-19 22:16:36 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 402 ms / 2,000 ms |
コード長 | 1,241 bytes |
コンパイル時間 | 1,911 ms |
コンパイル使用メモリ | 183,984 KB |
実行使用メモリ | 33,112 KB |
最終ジャッジ日時 | 2023-10-24 03:53:28 |
合計ジャッジ時間 | 4,726 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 8 ms
4,512 KB |
testcase_06 | AC | 39 ms
7,152 KB |
testcase_07 | AC | 50 ms
8,336 KB |
testcase_08 | AC | 259 ms
23,648 KB |
testcase_09 | AC | 63 ms
9,176 KB |
testcase_10 | AC | 400 ms
33,112 KB |
testcase_11 | AC | 402 ms
33,112 KB |
testcase_12 | AC | 393 ms
33,112 KB |
testcase_13 | AC | 2 ms
4,348 KB |
testcase_14 | AC | 2 ms
4,348 KB |
testcase_15 | AC | 2 ms
4,348 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define rep(i, s, n) for (int i = s; i < n; i++) #define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--) const long long MOD = 1e9 + 7, INF = 1e18; signed main() { int N, K; cin >> N >> K; map<int, int> mp; vector<int> a(N), b(N), v; for (int i = 0; i < N; i++) { cin >> a[i] >> b[i]; a[i]--; v.push_back(a[i]); v.push_back(b[i]); } sort(v.begin(), v.end()); int now = 0; map<int, int> inv; for (int i = 0; i < v.size(); i++) { if (mp.count(v[i]) == 0) { mp[v[i]] = now; inv[now] = v[i]; now++; } } vector<int> imos(now + 1, 0); for (int i = 0; i < N; i++) { imos[mp[a[i]]] += 1; imos[mp[b[i]]] -= 1; } for (int i = 0; i < now; i++) { imos[i + 1] += imos[i]; } rep(i, 0, now) { if (K - imos[i] * (inv[i + 1] - inv[i]) <= 0) { cout << inv[i] + (K + imos[i] - 1) / imos[i] << endl; return 0; } else { K -= imos[i] * (inv[i + 1] - inv[i]); } } }