제출 #868390

#제출 시각아이디문제언어결과실행 시간메모리
868390smirichtoCloud Computing (CEOI18_clo)C++17
54 / 100
574 ms2448 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back #define pi pair<ll,ll> #define F first #define S second #define all(x) (x).begin(), (x).end() #define alll(x) ((x).begin()+1), (x).end() #define clean(v) (v).resize(distance((v).begin(), unique(all(v)))); #define yes cout<<"Yes"<<endl; #define no cout<<"No"<<endl; #define mod mod #define endl '\n' mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 998244353; void io() { ios::sync_with_stdio(false); cin.tie(NULL); } template<class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<class T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } void nop() { cout << -1 << endl; return; } const ll N = 1e5+5 ; array<ll,4> tab[N] ; void solve() { ll n; cin>>n ; for(ll i = 1 ; i<=n ; i++){ cin>>tab[i][1]>>tab[i][0]>>tab[i][2] ; tab[i][3] = 1 ; } ll m ; cin>>m ; for(ll j = 1 ; j<=m ; j++){ ll i = j + n ; cin>>tab[i][1]>>tab[i][0]>>tab[i][2] ; } vector<ll> dp(n * 55 , -1e17) ; sort(tab+1 , tab+1+n+m) ; reverse(tab+1 , tab+1+n+m) ; dp[0] = 0 ; for(ll i = 1 ; i<=n + m ; i++){ vector<ll> ndp(n * 55 , -1e17) ; if(tab[i][3]){ for(ll j = 0 ; j<=n * 50 ; j++){ ckmax(ndp[j] , dp[j]) ; if(j + tab[i][1] <= n * 50) ckmax(ndp[j + tab[i][1]] , dp[j] - tab[i][2]) ; } } else{ for(ll j = 0 ; j<=n * 50 ; j++){ ckmax(ndp[j] , dp[j]) ; if(j>=tab[i][1]){ ckmax(ndp[j - tab[i][1]] , dp[j] + tab[i][2]) ; } } } dp.swap(ndp) ; } ll ans = 0 ; for(ll i = 0 ; i<=n*50 ; i++) ckmax(ans , dp[i]) ; cout<<ans<<endl; } int main() { io(); ll tt = 1; //cin>>tt ; while (tt--) { 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...