結果
問題 | No.1008 Bench Craftsman |
ユーザー | kotamanegi |
提出日時 | 2020-03-06 22:29:05 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 545 ms / 2,000 ms |
コード長 | 2,704 bytes |
コンパイル時間 | 2,273 ms |
コンパイル使用メモリ | 137,312 KB |
実行使用メモリ | 12,540 KB |
最終ジャッジ日時 | 2023-08-20 14:12:56 |
合計ジャッジ時間 | 11,332 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,132 KB |
testcase_01 | AC | 5 ms
8,044 KB |
testcase_02 | AC | 4 ms
8,068 KB |
testcase_03 | AC | 5 ms
8,128 KB |
testcase_04 | AC | 5 ms
8,168 KB |
testcase_05 | AC | 545 ms
12,444 KB |
testcase_06 | AC | 100 ms
10,312 KB |
testcase_07 | AC | 3 ms
8,124 KB |
testcase_08 | AC | 5 ms
8,264 KB |
testcase_09 | AC | 483 ms
9,732 KB |
testcase_10 | AC | 443 ms
12,460 KB |
testcase_11 | AC | 445 ms
12,540 KB |
testcase_12 | AC | 443 ms
12,476 KB |
testcase_13 | AC | 445 ms
12,468 KB |
testcase_14 | AC | 422 ms
12,488 KB |
testcase_15 | AC | 299 ms
12,468 KB |
testcase_16 | AC | 320 ms
12,468 KB |
testcase_17 | AC | 286 ms
12,392 KB |
testcase_18 | AC | 324 ms
12,472 KB |
testcase_19 | AC | 327 ms
12,512 KB |
testcase_20 | AC | 142 ms
10,160 KB |
testcase_21 | AC | 187 ms
9,672 KB |
testcase_22 | AC | 426 ms
9,776 KB |
testcase_23 | AC | 467 ms
10,916 KB |
testcase_24 | AC | 496 ms
10,448 KB |
testcase_25 | AC | 107 ms
10,352 KB |
testcase_26 | AC | 80 ms
9,596 KB |
testcase_27 | AC | 368 ms
9,464 KB |
testcase_28 | AC | 280 ms
10,984 KB |
testcase_29 | AC | 448 ms
11,692 KB |
コンパイルメッセージ
main.cpp:2:18: warning: '#pragma comment linker' ignored [-Wignored-pragmas] #pragma comment (linker, "/STACK:526000000") ^ 1 warning generated.
ソースコード
#define _CRT_SECURE_NO_WARNINGS #pragma comment (linker, "/STACK:526000000") #include "bits/stdc++.h" using namespace std; typedef string::const_iterator State; #define eps 1e-11L #define MAX_MOD 1000000007LL #define GYAKU 500000004LL #define MOD 998244353LL #define seg_size 262144 * 4LL #define pb push_back #define mp make_pair typedef long long ll; #define REP(a,b) for(long long (a) = 0;(a) < (b);++(a)) #define ALL(x) (x).begin(),(x).end() void init() { iostream::sync_with_stdio(false); cout << fixed << setprecision(20); } #define int ll vector<int> inputs; vector<int> mans[200000]; int n, m; int check(int border) { vector<int> color; REP(i, n) { color.push_back(0); } { priority_queue<pair<int, int>> next; int cnt = 0; int now = 0; for (int q = n - 1; q >= 0; --q) { for (auto x : mans[q]) { next.push(mp(q - (x+border) / border, x % border)); now += x + border; cnt++; } while (next.empty() == false&&next.top().first == q) { cnt--; now -= next.top().second; next.pop(); } now -= cnt * border; color[q] += now; } } { priority_queue<pair<int, int>> next; int cnt = 0; int now = 0; for (int q = 1; q < n; ++q) { for (auto x : mans[q-1]) { next.push(mp(-((q-1) + (x + border ) / border), x % border)); now += x; cnt++; } while (next.empty() == false&&next.top().first == -q) { cnt--; now -= next.top().second; next.pop(); } now -= cnt * border; color[q] += now; } } REP(i, n) { if (inputs[i] <= color[i]) return 0; } return 1; } void solve() { cin >> n >> m; REP(i, n) { int a; cin >> a; inputs.push_back(a); } int hoge = 0; REP(i, m) { int a, b; cin >> a >> b; a--; mans[a].push_back(b); hoge += b; } //check(2); int ok = 1; REP(i, inputs.size()) { if (hoge >= inputs[i]) { ok = 0; } } if (ok == 1) { cout << 0 << endl; return; } int bot = 1e9; int top = 0; while (bot - top > 1) { int mid = (top + bot) / 2; if (check(mid)) { bot = mid; } else { top = mid; } } if (bot == 1e9) bot = -1; cout << bot << endl; } #undef int int main() { init(); solve(); }