Submission #146325

#	Time	Username	Problem	Language	Result	Execution time	Memory
146325		aayush9	Cloud Computing (CEOI18_clo)	C++14	100 / 100	1537 ms	3444 KiB

clo

#include "bits/stdc++.h"

#define fast_cin() ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 10, M = 4e3 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 42;

struct st {
 int f, q, p;
 bool operator<(const st &o) const {
  return q > o.q;
 }
};

int f[M], q[M], p[M], F[M], Q[M], P[M];
vector<st> factories, requests;
ll dp[2][N];

int main() {
 fast_cin();
 int n; cin >> n;
 ll ans = 0;
 for (int i = 1; i <= n; ++i) {
  cin >> F[i] >> Q[i] >> P[i];
  for (int j = 0; j < F[i]; ++j) {
   factories.pb({1, Q[i], P[i]});
  }
  requests.pb({F[i], Q[i], P[i]});
  ans -= P[i];
 }
 int m; cin >> m;
 for (int i = 1; i <= m; ++i) {
  cin >> f[i] >> q[i] >> p[i];
  requests.pb({f[i], q[i], p[i]});
 }
 factories.pb({0, int(1e9) + 42, 0});
 requests.pb({0, int(1e9) + 42, 0});
 sort(factories.begin(), factories.end());
 sort(requests.begin(), requests.end());
 n = factories.size() - 1;
 m = requests.size() - 1;
 for (int i = 1; i <= m; ++i) {
  ll *cur = dp[i & 1];
  ll *prv = dp[1 - (i & 1)];
  cur[0] = 0;
  for (int j = 1; j <= n; ++j) {
   cur[j] = max(prv[j], cur[j - 1]);

   if (j >= requests[i].f and factories[j].q >= requests[i].q) {
    cur[j] = max(cur[j], prv[j - requests[i].f] + requests[i].p);
   }
  }
  // cout << cur[n] << '\n';
 }
 // cout << dp[m & 1][n] << " " << ans << '\n';
 cout << dp[m & 1][n] + ans << '\n';
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10