Submission #569725

#TimeUsernameProblemLanguageResultExecution timeMemory
569725MounirCloud Computing (CEOI18_clo)C++14
18 / 100
523 ms1316 KiB
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define print(x) cout << #x << " est " << x << endl;
#define x first
#define y second
#define int long long
using namespace std;

const int N = 1e5 + 5;
struct Transaction {
      int nCoeurs, freq, prix;

      bool operator < (const Transaction &autre) const {
            if (freq != autre.freq)
                  return freq > autre.freq;
            if (nCoeurs != autre.nCoeurs)
                  return nCoeurs > autre.nCoeurs;
            return prix < autre.prix;
      }
};

int dp[N];

signed main(){  
      int nPcs; cin >> nPcs;
      vector<Transaction> sac;
      while (nPcs--){
            Transaction pc; cin >> pc.nCoeurs >> pc.freq >> pc.prix;
            pc.prix = -pc.prix;
            sac.pb(pc);
      }

      int nVentes; cin >> nVentes;
      while (nVentes--){
            Transaction vente; cin >> vente.nCoeurs >> vente.freq >> vente.prix;
            vente.nCoeurs = -vente.nCoeurs;
            sac.pb(vente);
      }

      sort(all(sac));
      for (int i = 0; i < N; ++i)
            dp[i] = -1e9;
      dp[0] = 0;
      for (Transaction& trans : sac){
            if (trans.nCoeurs > 0){
                  for (int i = N - 1; i >= trans.nCoeurs; --i)
                        chmax(dp[i], dp[i - trans.nCoeurs] + trans.prix);
            }
            else {
                  trans.nCoeurs = abs(trans.nCoeurs);
                  for (int i = 0; i + trans.nCoeurs < N; ++i)
                        chmax(dp[i], dp[i + trans.nCoeurs] + trans.prix);
            }
      }

      int maxi = 0;
      for (int i = 0; i < N; ++i)
            chmax(maxi, dp[i]);
      cout << maxi << endl;
      return 0;   
}
#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...