Cod sursa(job #2971057)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 26 ianuarie 2023 13:03:03
Problema Stalpi Scor 0
Compilator cpp-64 Status done
Runda sa_fac_schema Marime 1.18 kb
#include <fstream>
#include <algorithm>
using namespace std;
/// stalpi

const int nmax = 5 * 1e4;
struct input {
  int poz, cost, st, dr;

}v[nmax + 1];

bool cmp (input a, input b){
  return a.cost < b.cost;
}
signed main(){

  ifstream fin ("stalpi.in");
  ofstream fout ("stalpi.out");

  int n;
  fin >> n;
  int minpoz = 1e9 + 1;
  int maxpoz = 0;
  for (int i = 1; i <= n; i++){
    fin >> v[i].poz >> v[i].cost >> v[i].st >> v[i].dr;
    v[i].st -= v[i].poz;
    v[i].dr += v[i].poz;
    minpoz = min (v[i].poz, minpoz);
    maxpoz = max (v[i].poz, maxpoz);
  }

  sort (v + 1, v + n + 1, cmp);

  int minst = v[1].st;
  int maxdr = v[1].dr;
  int s = v[1].cost;
  for (int i = 2; i <= n; i++){
    int ok = 0;
    if (v[i].st < minst){
      minst = v[i].st, s+=v[i].cost;
      if (v[i].dr > maxdr)
        maxdr = v[i].dr;
      ok ++;
    }

    if (v[i].dr > maxdr){
      maxdr = v[i].dr;
      s += v[i].cost;
      if (v[i].st < minst){
        minst = v[i].st;
      }
      ok ++;
    }
    if (ok == 2) s -= v[i].cost;

    if (minst <= minpoz && maxdr >= maxpoz){
      fout << s;
      return 0;
    }

  }
  return 0;
}