Submission #862213

#TimeUsernameProblemLanguageResultExecution timeMemory
862213yeediotTwo Dishes (JOI19_dishes)C++14
100 / 100
1915 ms246648 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define F first #define S second #define all(x) x.begin(),x.end() #define pii pair<int,int> #define pb push_back #define sz(x) (int)(x.size()) #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) #define vi vector<int> #define vp vector<pii> #define vvi vector<vi> //Don't open the standings during contests. const int mxn=1e6+5; vector<int>a(mxn),s(mxn),p(mxn),b(mxn),t(mxn),q(mxn); int pre[mxn],pre2[mxn]; vector<pii>pt[mxn]; int dif[mxn]; signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]>>s[i]>>p[i]; pre[i]=pre[i-1]+a[i]; } for(int i=1;i<=m;i++){ cin>>b[i]>>t[i]>>q[i]; pre2[i]=pre2[i-1]+b[i]; } int ans=0; for(int i=1;i<=n;i++){ if(pre[i]>s[i])continue; int x=upper_bound(pre2+1,pre2+m+1,s[i]-pre[i])-pre2; ans+=p[i]; if(x<=m)pt[i].pb({x,-p[i]}); } for(int j=1;j<=m;j++){ if(pre2[j]>t[j])continue; if(pre2[j]+pre[n]<=t[j])ans+=q[j]; else{ int y=upper_bound(pre+1,pre+n+1,t[j]-pre2[j])-pre; pt[y].pb({j,q[j]}); } } set<int>st; for(int i=0;i<=n;i++){ sort(all(pt[i])); for(auto [x,y]:pt[i]){ //cout<<x<<' '; if(!st.count(x)){ st.insert(x); dif[x]=0; } dif[x]+=y; } for(auto [x,fuck]:pt[i]){ //維護前綴max所以把dif<0的都刪掉 auto it=st.find(x); while(it!=st.end() and dif[*it]<0){ int temp=dif[*it]; it=st.erase(it); if(it!=st.end())dif[*it]+=temp; } } } for(auto i:st)ans+=dif[i]; cout<<ans<<'\n'; } /* input: 2 3 6 2 1 3 2 2 2 */

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:52:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         for(auto [x,y]:pt[i]){
      |                  ^
dishes.cpp:60:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         for(auto [x,fuck]:pt[i]){
      |                  ^
#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...