結果
問題 |
No.1919 Many Monster Battles
|
ユーザー |
![]() |
提出日時 | 2022-04-29 23:11:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,776 bytes |
コンパイル時間 | 3,072 ms |
コンパイル使用メモリ | 201,120 KB |
実行使用メモリ | 15,776 KB |
最終ジャッジ日時 | 2024-06-29 04:54:39 |
合計ジャッジ時間 | 7,928 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 21 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007; int main(){ int N; cin >> N; vector<int> a(N); for (int i = 0; i < N; i++){ cin >> a[i]; } vector<int> b(N); for (int i = 0; i < N; i++){ cin >> b[i]; } vector<long long> ans(2, 0); for (int i = 0; i < 2; i++){ vector<pair<int, int>> P(N); for (int j = 0; j < N; j++){ P[j] = make_pair(a[j], b[j]); } sort(P.begin(), P.end()); for (int j = 0; j < N; j++){ a[j] = P[j].first; b[j] = P[j].second; } vector<pair<int, int>> P2(N); for (int j = 0; j < N; j++){ P2[j] = make_pair(b[j], j); } sort(P2.begin(), P2.end()); vector<int> id(N); for (int j = 0; j < N; j++){ id[j] = P2[j].second; } vector<bool> used1(N, false); for (int j = 0; j < N; j++){ int p = id[j]; for (int k = 0; k < p; k++){ if (used1[k] && a[p] - b[p] > a[k] - b[k]){ ans[i] += a[p]; } } for (int k = p + 1; k < N; k++){ if (used1[k] && a[p] + b[p] < a[k] + b[k]){ ans[i] -= a[p]; } } used1[p] = true; } vector<bool> used2(N, false); for (int j = N - 1; j >= 0; j--){ int p = id[j]; for (int k = 0; k < p; k++){ if (used2[k] && a[p] + b[p] > a[k] + b[k]){ ans[i] += a[p]; } } for (int k = p + 1; k < N; k++){ if (used2[k] && a[p] - b[p] < a[k] - b[k]){ ans[i] -= a[p]; } } used2[p] = true; } ans[i] %= MOD; ans[i] += MOD; ans[i] *= 2; ans[i] %= MOD; swap(a, b); } cout << ans[0] << ' ' << ans[1] << endl; }