제출 #617223

#제출 시각아이디문제언어결과실행 시간메모리
617223erkamCloud Computing (CEOI18_clo)C++17
100 / 100
617 ms7484 KiB
#include<bits/stdc++.h> #define st first #define nd second using namespace std; const int N=200005,mod=1000000007; int n,m,k,l,x,h[N]; long long dp[N],nxt[N]; vector<int>v[N]; pair<pair<int,bool>,pair<int,int> > arr[N]; int main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); cin >> n; for(int i=1;i<=n;i++){ cin >> arr[i].nd.st >> arr[i].st.st >> arr[i].nd.nd; arr[i].st.nd=1; } cin >> m; for(int i=1;i<=m;i++){ cin >> arr[n+i].nd.st >> arr[n+i].st.st >> arr[n+i].nd.nd; arr[n+i].st.nd=0; } sort(arr+1,arr+n+m+1); reverse(arr+1,arr+n+m+1); long long sum=0; for(int i=1;i<N;i++)dp[i]=-1e18; for(int i=1;i<=n+m;i++){ if(arr[i].st.nd==1){ sum+=arr[i].nd.st; for(int j=0;j<=sum;j++){ nxt[j]=dp[j]; if(j>=arr[i].nd.st){ nxt[j]=max(nxt[j],dp[j-arr[i].nd.st]-arr[i].nd.nd); } } } else{ for(int j=sum;j>=0;j--){ nxt[j]=dp[j]; if(j+arr[i].nd.st<=sum){ nxt[j]=max(nxt[j],dp[j+arr[i].nd.st]+arr[i].nd.nd); } } } for(int j=0;j<=sum;j++){ dp[j]=nxt[j]; } } long long ans=0; for(int i=0;i<=sum;i++){ ans=max(ans,dp[i]); } cout << ans << endl; }
#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...