제출 #482303

#제출 시각아이디문제언어결과실행 시간메모리
482303Blistering_BarnaclesCloud Computing (CEOI18_clo)C++11
36 / 100
48 ms31076 KiB
//apig's property //Happiness can be found, even in the darkest of times, if one only remembers to turn on the light //El Pueblo Unido Jamas Sera Vencido //Do or do not... there is no try //Billions of bilious blue blistering barnacles in a thundering typhoon! #include<bits/stdc++.h> #define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) #define F first #define S second #define pb push_back #define vll vector< ll > #define vi vector< int > #define pll pair< ll , ll > #define pi pair< int , int > #define all(s) s.begin() , s.end() #define sz(s) s.size() #define str string #define md ((s + e) / 2) #define mid ((l + r) / 2) #define msdp(dp) memset(dp , -1 , sizeof dp) #define mscl(dp) memset(dp , 0 , sizeof dp) #define C continue #define R return #define B break #define lx node * 2 #define rx node * 2 + 1 #define br(o) o ; break #define co(o) o ; continue #define f F.F #define v F.S #define t S.F #define c S.S using namespace std; typedef long long ll; ll q , dp[50005][5] , b[555555], k, l, m, n, o, p; map < ll , ll > mp; vll adj[555555]; const ll mod = 1e9+7; str s; pair < pll , pll > a[555555] ; ll cmp(const pair < pll , pll > &a , const pair < pll , pll > &b){ if(a.f == b.f)R a.t < b.t ; R a.f > b.f ; } void solve(){ ll nn = 0 ; cin >> n ; o = 0 ; for(ll i = 1 ; i <= n ; i++){ ll cc , ff , vv ; cin >> cc >> ff >> vv ; nn += cc ; a[++o] = {{ff , vv} , {1LL , cc}} ; } cin >> m ; for(ll i = 1 ; i <= m ; i++){ ll cc , ff , vv ; cin >> cc >> ff >> vv ; a[++o] = {{ff , vv} , {2LL , cc}} ; } ll ans = -1e15 ; sort(a + 1 , a + o + 1 , cmp) ; for(ll j = 1 ; j <= nn ; j++){ dp[j][0] = -1e12 ; } for(ll i = 1 ; i <= o ; i++){ for(ll j = 0 ; j <= nn ; j++){ dp[j][i & 1] = dp[j][!(i & 1)] ; if(a[i].t == 2){ if(j + a[i].c <= nn){ dp[j][i & 1] = max(dp[j][i & 1] , dp[j + a[i].c][!(i & 1)] + a[i].v) ; } } else { if(j - a[i].c >= 0){ dp[j][i & 1] = max(dp[j][i & 1] , dp[j - a[i].c][!(i & 1)] - a[i].v) ; } } //cout << i << " " << j << " " << dp[j][i & 1] << " " << a[i].t << endl ; ans = max(ans , dp[j][i & 1]) ; } } cout << ans << endl ; } int main(){ fast ; q = 1 ; //cin >> q ; while(q--){ solve() ; } }
#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...