Cod sursa(job #1895176)

Utilizator MaligMamaliga cu smantana Malig Data 27 februarie 2017 20:28:41
Problema Lupul Urias si Rau Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");

const int NMax = 100000 + 5;

int N,X,L;
long long dp[NMax][1002];

struct elem {
    int dist,val,step;
}v[NMax];

bool cmp (elem a,elem b) {
    if (a.step == -1) {
        return false;
    }
    if (b.step == -1) {
        return true;
    }
    return a.dist<b.dist;
}

const int strMax = 100005 * 30;
char str[strMax];
int pos = 0;

int getNumber() {
    int nr = 0;
    while (!('0'<=str[pos] && str[pos]<='9')) {
        ++pos;
    }

    while ('0'<=str[pos] && str[pos]<='9') {
        nr = nr * 10 + str[pos++] - '0';
    }
    return nr;
}

int main() {
    in.getline(str,strMax,'%');
    N = getNumber();
    X = getNumber();
    L = getNumber();

    int MAX_STEP = 0;
    for (int i=1;i<=N;++i) {
        v[i].dist = getNumber();
        v[i].val = getNumber();
        v[i].step = (v[i].dist > X) ? -1 : (X - v[i].dist)/L;
        if (MAX_STEP < v[i].step) {
            MAX_STEP = v[i].step;
        }
    }

    ++MAX_STEP;
    for (int i=1;i<=N;++i) {
        v[i].step = MAX_STEP - v[i].step;
    }

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

    /*
    for (int i=1;i<=N;++i) {
        cout<<v[i].dist<<' '<<v[i].val<<' '<<v[i].step<<'\n';
    }
    cout<<"\n\n";
    //*/

    int minDist = v[1].dist;
    if (minDist > X) {
        out<<0;
        return 0;
    }

    /*
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=MAX_STEP;++j) {
            cout<<dp[i][j]<<' ';
        }
        cout<<'\n';
    }
    cout<<'\n';
    //*/

    for (int j=1;j<=MAX_STEP;++j) {
        for (int i=1;i<=N;++i) {
            bool available = (v[i].step<=j) ? true : false;

            dp[i][j] = dp[i-1][j];
            if (available && dp[i][j] < dp[i-1][j-1] + v[i].val) {
                dp[i][j] = dp[i-1][j-1] + v[i].val;
            }
        }
    }

    /*
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=MAX_STEP;++j) {
            cout<<dp[i][j]<<' ';
        }
        cout<<'\n';
    }
    cout<<'\n';
    //*/

    out<<dp[N][MAX_STEP];
    return 0;
}