Submission #569726

#	Time	Username	Problem	Language	Result	Execution time	Memory
569726		Mounir	Cloud Computing (CEOI18_clo)	C++14	100 / 100	545 ms	1356 KiB

clo

#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] = -1e18;
      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;   
}

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