제출 #585893

#제출 시각아이디문제언어결과실행 시간메모리
585893LucppTwo Dishes (JOI19_dishes)C++17
100 / 100
2152 ms191504 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; const int MAX = 1e6+2; ll A[2][MAX], T[2][MAX], P[2][MAX]; int n[2], B[2][MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n[0] >> n[1]; for(int i = 0; i < 2; i++){ A[i][0] = 0; for(int j = 1; j <= n[i]; j++){ cin >> A[i][j] >> T[i][j] >> P[i][j-1]; A[i][j] += A[i][j-1]; } } for(int i = 0; i < 2; i++){ for(int j = 1; j <= n[i]; j++){ if(A[i][j] > T[i][j]) B[i][j-1] = -1; else if(A[i][j]+A[1-i][n[1-i]] <= T[i][j]) B[i][j-1] = n[1-i]; else B[i][j-1] = (int)(upper_bound(A[1-i], A[1-i]+n[1-i], T[i][j]-A[i][j])-A[1-i]-1); // cerr << B[i][j-1] << " "; } // cerr << "\n"; } vector<vector<int>> todo(n[0]+2); ll sum = 0; for(int i = 0; i < n[1]; i++){ if(B[1][i] > -1) todo[B[1][i]].push_back(i), sum += P[1][i]; } map<int, ll> s; set<int> toCorrect; s.emplace(0, sum); auto correct = [&](int i){ auto it = s.find(i); if(it == s.end() || it->second >= 0) return; ll x = it->second; while(true){ it = s.erase(it); if(it == s.end()) break; it->second += x; if(it->second >= 0) break; x = it->second; } }; auto upd = [&](int i, ll v){ s[0] += v; s[i+1] += -v; // toCorrect.insert(0); toCorrect.insert(i+1); }; for(int i = 0; i < n[0]; i++){ toCorrect.clear(); if(B[0][i] > -1) upd(B[0][i], P[0][i]); for(int j : todo[i]){ upd(j, -P[1][j]); } for(int j : toCorrect) correct(j); // cerr << i << ":\n"; // for(auto [j, x] : s){ // cerr << " " << j << " " << x << "\n"; // } } ll ans = 0; for(auto [i, x] : s) if(i <= n[1]) ans += x; cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...