Submission #569687

#	Time	Username	Problem	Language	Result	Execution time	Memory
569687		Mounir	Cloud Computing (CEOI18_clo)	C++14	0 / 100	33 ms	7376 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 = 2e5, OO = 1e18;
int iPc[N], prixPc[N];
int nPcs;
int maxGain[N];
vector<pii> commandes[N]; //first : taille de la commande, second : gain de la commande
bool vu[N];

struct Pc {
      int nCoeurs, val, prix;

      bool operator < (const Pc &autre) const {
            if (val != autre.val)
                  return val < autre.val;
            if (prix != autre.prix)
                  return prix < autre.prix;
            return nCoeurs < autre.nCoeurs;
      }
};

int getSum(int deb, int fin){
      int sum = prixPc[fin];
      if (deb != 0)
            sum -= prixPc[deb - 1];
      return sum;
}

struct Coeur {
      int val, prix;
};

int nCoeurs = 0;

signed main(){  
      for (int i = 0; i < N; ++i)
            maxGain[i] = -OO;
      cin >> nPcs;
      vector<Pc> pcs(nPcs);
      for (Pc& pc : pcs)
            cin >> pc.nCoeurs >> pc.val >> pc.prix;

      sort(all(pcs));
      vector<Coeur> coeurs;
      int id = 0;
      for (Pc pc : pcs){
            for (int i = 0; i < pc.nCoeurs; ++i){
                  coeurs.pb({pc.val, pc.prix});
                  iPc[sz(coeurs) - 1] = id;
            }
            prixPc[id] = pc.prix;
            nCoeurs += pc.nCoeurs;
            id++;
      }
      iPc[nCoeurs] = nPcs - 1;

      for (int i = 1; i < nPcs; ++i)
            prixPc[i] += prixPc[i - 1];

      int nCommandes; cin >> nCommandes;
      vector<Pc> commandes(nCommandes);
      for (Pc& commande : commandes)
            cin >> commande.nCoeurs >> commande.val >> commande.prix;
      sort(all(commandes));
      reverse(all(commandes));
      for (Pc commande : commandes){
        //    cout << "commande " << commande.nCoeurs << " " << commande.val << " " << commande.prix << endl;
            for (int i = 0; i + commande.nCoeurs <= nCoeurs; ++i){
                  if (coeurs[i].val < commande.val) continue;
                  int coutLocation = getSum(iPc[i], iPc[i + commande.nCoeurs]);
                  chmax(maxGain[i], commande.prix - coutLocation);
                  if (i + commande.nCoeurs >= nCoeurs) continue;
                  if (iPc[i + commande.nCoeurs] == iPc[i + commande.nCoeurs - 1]) 
                        coutLocation -= getSum(iPc[i + commande.nCoeurs], iPc[i + commande.nCoeurs]);
                  chmax(maxGain[i], maxGain[i + commande.nCoeurs] + commande.prix - coutLocation);
            }
/*
            for (int i = 0; i < nCoeurs - 1; ++i)
                  cout << maxGain[i] << " ";
            cout << endl;*/

            vector<int> maxPourPc(nPcs, -OO);
            int maxGlobal = -OO;
            for (int i = nCoeurs - 1; i >= 0; --i){
              /*    chmax(maxPourPc[iPc[i]], maxGain[i]);
                  chmax(maxGlobal, maxGain[i]);
                  if (i == 0 || iPc[i] == iPc[i - 1])
                        chmax(maxGain[i], max(maxGlobal - getSum(iPc[i], iPc[i]), maxPourPc[iPc[i]]));
                  else*/
                        chmax(maxGain[i], maxGlobal - getSum(iPc[i], iPc[i]));
                        chmax(maxGlobal, maxGain[i]);
            }
         /*   for (int i = 0; i < nCoeurs - 1; ++i)
                  cout << maxGain[i] << " ";
            cout << endl;*/
      }

      int res = 0;
      for (int i = 0; i < nCoeurs; ++i)
            chmax(res, maxGain[i]);
      cout << res << endl;
      return 0;   
}

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