Pagini recente » Cod sursa (job #3203473) | Cod sursa (job #392184) | Cod sursa (job #2755515) | Cod sursa (job #1983901) | Cod sursa (job #137193)
Cod sursa(job #137193)
#include <cstdio>
#include <algorithm>
using namespace std;
// const long MAX=100010; //TODO de modificat la loc
const long MAX = 10;
struct stalp {
long x,c,st,dr;
} S[MAX];
int comp(const stalp &A, const stalp &B) { return A.x<B.x; }
long n, sum;
long Cost[MAX], T[MAX];
bool ok[MAX];
void solve1() {
sort(S, S+n, comp);
memset(Cost, 0x3f, sizeof(long)*(n+2));
for (long i=0; i<n; ++i) {
if ( Cost[i]>S[i].c )
Cost[i] = S[i].c, T[i] = i;
long delta = S[i].x-S[i].st;
for (long j=i-1; j>=0 && S[j].x>=delta; --j)
if ( Cost[j]>S[i].c )
Cost[j]=S[i].c, T[j] = i;
delta = S[i].x+S[i].dr;
for (long j=i+1; j<n && S[j].x<=delta; ++j)
if ( Cost[j]>S[i].c )
Cost[j]=S[i].c, T[j] = i;
}
sum = 0;
for (long i=0; i<n; ++i)
if ( !ok[T[i]] )
sum += S[T[i]].c, ok[T[i]] = 1;
return ;
for (long i=0; i<n; ++i)
printf("%ld\n", T[i]);
}
int main() {
freopen("stalpi.in", "r", stdin);
scanf("%ld", &n);
for (long i=0; i<n; ++i)
scanf("%ld %ld %ld %ld", &S[i].x, &S[i].c, &S[i].st, &S[i].dr);
fclose(stdin);
solve1();
fprintf(fopen("stalpi.out","w"), "%ld\n", sum);
return 0;
}