Pagini recente » Cod sursa (job #1967892) | Cod sursa (job #3232639) | Cod sursa (job #2772423) | Cod sursa (job #2612576) | Cod sursa (job #3001147)
#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];
}