Submission #784791

#TimeUsernameProblemLanguageResultExecution timeMemory
784791mgl_diamondCloud Computing (CEOI18_clo)C++14
100 / 100
604 ms2092 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"
 
void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".in", "r")) {
    freopen(file".in", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 1000;
const int M = 5005;
const int D = 11;
const int MOD = 1e9+7;
void add(int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

struct object {
  int t, c, f, v;
  object(int _t=0, int _c=0, int _f=0, int _v=0) : t(_t), c(_c), f(_f), v(_v) {}
  bool operator < (const object &b) const { return make_pair(f, t) > make_pair(b.f, b.t); }
};

const ll LINF = 1e18;
const int INF = 1e9;
int n, m;
ll dp[2][2000*50+1];
vector<object> a;

int main() {
  setIO();
    
  cin >> n;

  foru(i, 1, n) {
    int c, f, v;
    cin >> c >> f >> v;
    a.emplace_back(1, c, f, v);
  }

  cin >> m;

  foru(i, 1, m) {
    int c, f, v;
    cin >> c >> f >> v;
    a.emplace_back(0, c, f, v);
  }

  sort(all(a));
  memset(dp[0], -0x3f, sizeof(dp[0]));
  dp[0][0] = 0;

  int sum = 0;
  foru(i, 0, sz(a)-1) {
    int at = i&1, nxt = at^1;
    memset(dp[nxt], -0x3f, sizeof(dp[nxt]));
    foru(j, 0, sum) if (dp[at][j] > -LINF) {
      ll cur = dp[at][j];
      dp[nxt][j] = max(dp[nxt][j], dp[at][j]);
      if (a[i].t) {
        dp[nxt][j+a[i].c] = max(dp[nxt][j+a[i].c], cur - a[i].v);
      }
      else {
        if (j >= a[i].c) dp[nxt][j-a[i].c] = max(dp[nxt][j-a[i].c], cur + a[i].v);
      }
    }
    if (a[i].t) {
      sum += a[i].c;
    }
  }

  cout << *max_element(dp[(n+m)&1], dp[(n+m)&1]+sum+1);
}

Compilation message (stderr)

clo.cpp: In function 'void setIO()':
clo.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen(file".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
clo.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...