제출 #565017

#제출 시각아이디문제언어결과실행 시간메모리
565017KarukCloud Computing (CEOI18_clo)C++14
100 / 100
508 ms1524 KiB
#include<bits/stdc++.h> #define min(A,B) (A<B?A:B) #define max(A,B) (A>B?A:B) using namespace std; long long dp[150000]; void solve() { int n; cin>>n; vector<vector<long long> >a; for(int i=0;i<n;i++) { long long f,v,c; cin>>c>>f>>v; a.push_back({f,c,-v}); } int m; cin>>m; for(int i=0;i<m;i++) { long long f,v,c; cin>>c>>f>>v; a.push_back({f,-c,v}); } sort(a.begin(),a.end()); for(int i=1;i<=n+m;i++) { int maxs=min(100000,100+50*min(i,n+m-i)); if(a[i-1][1]<0) { for(int negcores=maxs;negcores>=-a[i-1][1];negcores--) { dp[negcores]=max(dp[negcores],dp[negcores+a[i-1][1]]+a[i-1][2]); } } else { for(int negcoresfrom=0;negcoresfrom-a[i-1][1]<=maxs;negcoresfrom++) { dp[max(0,negcoresfrom-a[i-1][1])]=max(dp[max(0,negcoresfrom-a[i-1][1])],dp[negcoresfrom]+a[i-1][2]); } } } cout<<dp[0]<<endl; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); solve(); return 0; }
#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...