Submission #1334188

#TimeUsernameProblemLanguageResultExecution timeMemory
1334188vyaductCloud Computing (CEOI18_clo)C++20
18 / 100
277 ms1240 KiB
#include<bits/stdc++.h>
using namespace std;

#define REP(i, from, to) for (ll i=(from);i<=(to);++i)
#define PER(i, from, to) for (ll i=(from);i>=(to);--i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (ll)(x).size()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
 
void solve(){
  int n; cin>>n;
  vector<array<ll, 3>> a(n);
  int sum = 0;
  REP(i, 0, n-1) {
    cin>>a[i][0]>>a[i][1]>>a[i][2];
    sum += a[i][0];
  }

  int m; cin>>m;
  deque<array<ll, 3>> b(m);
  REP(j, 0, m-1) cin>>b[j][0]>>b[j][1]>>b[j][2];

  const ll INF = 1e18;
  vll dp(sum+1, -INF);

  dp[0] = 0;
  REP(i, 0, n-1){
    PER(x, sum, a[i][0]){
      dp[x] = max(dp[x], dp[x-a[i][0]] - a[i][2]);
    }
  }

  REP(i, 0, m-1){
    REP(x, 0, sum-b[i][0]){
      dp[x] = max(dp[x], dp[x+b[i][0]] + b[i][2]);
    }
  }
 
  ll best = 0;
  REP(x, 0, sum) best = max(best, dp[x]);
  cout << best << endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt=1;
  // cin>>tt;
  while(tt--) 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...