Cod sursa(job #3001147)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 13 martie 2023 11:46:02
Problema Stalpi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;


class InParser {
    vector<char> str;
    int ptr;
    ifstream fin;

    char getChar() {
        if (ptr == int(str.size())) {
            fin.read(str.data(), str.size());
            ptr = 0;
        }
        return str[ptr++];
    }

    template<class T>
    T getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + chr - '0';
            chr = getChar();
        }
        return sgn * num;
    }

public:
    InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
    ~InParser() { fin.close(); }

    template<class T>
    friend InParser& operator>>(InParser& in, T& num) {
        num = in.getInt<T>();
        return in;
    }
};

const int NMAX = 1e5 + 1;

struct stalp
{
    int x,ind,cost,st,dr;
};

struct oferta
{
    int st , dr, c;
    bool operator <(const oferta lhs) const
    {
        return lhs.st > st;
    }
};


oferta oferte[NMAX + 1];
long long dp[NMAX + 1];

bool cmp(const stalp &a,const stalp &b){return a.x < b.x;}


stalp v[NMAX];

int main()
{
    InParser fin("stalpi.in");
    ofstream cout("stalpi.out");
    int n; fin >> n;
    for(int i = 1; i <= n ; i++)
        {
            fin >> v[i].x >> v[i].cost >> v[i].st >> v[i].dr;
        }

    sort(v + 1,v + 1 + n,cmp); int maxpas = 1; while(maxpas < n) maxpas <<= 1;
    for(int i = 1; i <= n ; i++)
        {
            ///ultimul din stanga cu proprietatea ca care.x + v[i].st >= v[i].x
            oferta &now = oferte[i]; int minstanga = v[i].x - v[i].st;
            int ans = 0; for(int pas = maxpas ; pas ; pas >>= 1) if(ans + pas + 1 <= n && v[ans + pas].x  < minstanga) ans += pas;
            now.st = ans + 1; ans = 0; for(int pas = maxpas ; pas ; pas >>= 1) if(ans + pas <= n && v[ans + pas].x <= v[i].x + v[i].dr) ans += pas;
            now.dr = ans; now.c = v[i].cost;
        }

    sort(oferte + 1 , oferte + 1 + n);


    for(int i = 1;i <= n;i++)
        {
            dp[i] = 1LL << 60;
        }

    for(int j = 1;j <= n ;j++)
        {
            int dreapta = oferte[j].dr;
            int stanga = oferte[j].st;
            int cost = oferte[j].c;

            if((dp[stanga - 1] + cost) < dp[dreapta])
                {
                    dp[dreapta] = dp[stanga - 1] + cost;
                    for(int i = stanga; i<=dreapta ; i++)
                        {
                            dp[i] = min(dp[i] , dp[dreapta]);
                        }
                }
        }

    cout << dp[n];
}