結果
問題 |
No.1708 Quality of Contest
|
ユーザー |
![]() |
提出日時 | 2024-03-10 08:29:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 334 ms / 2,000 ms |
コード長 | 2,016 bytes |
コンパイル時間 | 1,171 ms |
コンパイル使用メモリ | 134,240 KB |
最終ジャッジ日時 | 2025-02-20 03:37:10 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <array> #include <iterator> #include <string> #include <cctype> #include <cstring> #include <cstdlib> #include <cassert> #include <cmath> #include <ctime> #include <iomanip> #include <numeric> #include <stack> #include <queue> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <bitset> #include <random> #include <utility> #include <functional> using namespace std; void Main() { int N,M,X; cin >> N >> M >> X; vector<int> A(N),B(N); vector<vector<int>> G(M); for(int i = 0;i < N;i++) { cin >> A[i] >> B[i]; B[i]--; G[B[i]].push_back(A[i]); } int K; cin >> K; vector<int> C(N + 1); for(int i = 0;i < K;i++) { int c; cin >> c; C[c]++; } multiset<pair<int,int>> S,T; for(int i = 0;i < N;i++) { S.insert(make_pair(A[i],B[i])); } vector<int> Q; Q.reserve(N); vector<int> nw(N); for(int i = 0;i < N;i++) { if(T.empty()) { pair<int,int> P = *S.rbegin(); nw[i] = 1; Q.push_back(P.first); for(int a : G[P.second]) { auto it = S.find(make_pair(a,P.second)); S.erase(it); T.insert(make_pair(a,P.second)); } T.erase(T.find(P)); } else if(S.empty()) { pair<int,int> P = *T.rbegin(); Q.push_back(P.first); T.erase(T.find(P)); } else { pair<int,int> L = *S.rbegin(),R = *T.rbegin(); if(L.first + X > R.first) { nw[i] = 1; Q.push_back(L.first); for(int a : G[L.second]) { auto it = S.find(make_pair(a,L.second)); S.erase(it); T.insert(make_pair(a,L.second)); } T.erase(T.find(L)); } else { Q.push_back(R.first); T.erase(T.find(R)); } } } long long ans = 0; int cnt = 0; long long sum = 0; for(int i = 0;i < N;i++) { if(nw[i]) { cnt++; } sum += Q[i]; ans += (sum + (long long) X * cnt) * C[i + 1]; } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) Main(); }