Submission #1334227

#TimeUsernameProblemLanguageResultExecution timeMemory
1334227vyaductCloud Computing (CEOI18_clo)C++20
72 / 100
749 ms2628 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 R = 0, L = 0;
  REP(i, 0, n-1) {
    cin>>a[i][0]>>a[i][1]>>a[i][2];
    R += a[i][0];
  }

  int m; cin>>m;
  REP(j, 0, m-1) {
    array<ll, 3> b;
    cin>>b[0]>>b[1]>>b[2];
    L += b[0]; b[0]*=-1; b[2]*=-1;
    a.push_back(b);
  }

  sort(ALL(a), [&](auto x, auto y){ return x[1] > y[1]; });

  const ll INF = 1e18;
  vector<vll> dp(2, vll(R+1, -INF));

  dp[0][0] = 0;
  REP(i, 0, n+m-1){
    REP(x, 0, R){
      dp[1][x] = max(dp[1][x], dp[0][x]);
      if (x-a[i][0] < 0) continue;
      if (x-a[i][0] > R) continue;
      dp[1][x] = max(dp[1][x], dp[0][x-a[i][0]] - a[i][2]);
    }
    REP(x, 0, R) {
      dp[0][x] = dp[1][x];
      dp[1][x] = -INF;
    }
  }

  ll best = 0;
  REP(x, 0, R) best = max(best, dp[0][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...