제출 #1333656

#제출 시각아이디문제언어결과실행 시간메모리
1333656vyaductCloud Computing (CEOI18_clo)C++20
18 / 100
267 ms1952 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 dp1(sum+1, INF), dp2(sum+1, 0);

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

  REP(i, 0, m-1){
    PER(x, sum, b[i][0]){
      dp2[x] = max(dp2[x], dp2[x-b[i][0]] + b[i][2]);
    }
  }
 
  ll best = 0;
  REP(x, 0, sum) best = max(best, dp2[x] - dp1[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...