제출 #1079140

#제출 시각아이디문제언어결과실행 시간메모리
1079140azberjibiouTwo Dishes (JOI19_dishes)C++17
100 / 100
1741 ms317572 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define all(v) v.begin(), v.end() #define pb push_back #define lb lower_bound #define gibon ios::sync_with_stdio(false); cin.tie(0); #define fi first #define se second #define pii pair<int, int> #define pll pair<ll, ll> typedef long long ll; using namespace std; const int mxN=1005000; const int mxM=1557; const int mxK=60; const ll INF=1e18; int N, M; ll A[mxN], B[mxN], S[mxN], P[mxN], T[mxN], Q[mxN]; ll pA[mxN], pB[mxN]; vector <pll> cont[mxN]; ll C; void input(){ cin >> N >> M; for(int i=1;i<=N;i++){ cin >> A[i] >> S[i] >> P[i]; } for(int i=1;i<=M;i++){ cin >> B[i] >> T[i] >> Q[i]; } } void make_prefix(){ for(int i=1;i<=N;i++) pA[i]=pA[i-1]+A[i]; for(int i=1;i<=M;i++) pB[i]=pB[i-1]+B[i]; } void make_score(){ for(int i=1;i<=N;i++){ if(S[i]<pA[i]) continue; ll t=S[i]-pA[i]; if(t>=pB[M]){ C+=P[i]; continue; } int idx=lower_bound(pB, pB+M+1, t+1)-pB-1; cont[i].emplace_back(idx, P[i]); } for(int i=1;i<=M;i++){ if(T[i]<pB[i]) continue; ll x=T[i]-pB[i]+1, y=pB[i]-1; if(x>pA[N]){ C+=Q[i]; continue; } int ix=lower_bound(pA, pA+N+1, x)-pA, iy=i-1; C+=Q[i]; cont[ix].emplace_back(iy, -Q[i]); } } void push_set(multiset <pll> &s, pll now){ if(now.se>0){ s.insert(now); return; } ll x=-now.se; auto it=s.lower_bound(now); while(x>0){ //printf("x=%lld, it=%lld %lld\n", x, it->fi, it->se); if(it->se >=x){ s.insert(pll(it->fi, it->se - x)); s.erase(it); return; } else{ x-= it->se; auto nit=it; nit++; s.erase(it); it=nit; } } } void make_dp(){ multiset <pll> s; s.insert(pll(INF, INF)); for(int i=1;i<=N;i++){ sort(all(cont[i]), [](pll a, pll b){return a.se<b.se;}); //printf("i=%d\n", i); for(auto [pos, val] : cont[i]){ //printf("(%lld %lld) ", pos, val); C+=val; push_set(s, pll(pos, -val)); } //printf("\n"); //printf("C=%lld\n", C); //for(pll x : s) printf("(%lld %lld) ", x.fi, x.se); //printf("\n"); } auto it=s.end(); it--; s.erase(it); for(auto x : s) C+=x.se; cout << C << '\n'; } int main(){ gibon input(); make_prefix(); make_score(); make_dp(); }

컴파일 시 표준 에러 (stderr) 메시지

dishes.cpp: In function 'void make_score()':
dishes.cpp:49:28: warning: unused variable 'y' [-Wunused-variable]
   49 |         ll x=T[i]-pB[i]+1, y=pB[i]-1;
      |                            ^
#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...