Cod sursa(job #1895272)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 27 februarie 2017 21:09:59
Problema Lupul Urias si Rau Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMax = 100000 + 5;

// rezolvare cu programare dinamica, nu poate lua punctaj maxim din cauza
// problemelor de eficienta si memorie

int N,X,L;
long long dp[NMax][2002];
// dp[i][j] = cantitatea maxima de lana care se poate obtine din primele i oi pana in momentul j
// unde momentele se iau in ordine inversa si inseamna numarul maxim de miscari pe care le face lupul

struct elem {
    int dist,val,step;
}v[NMax];
// v[i].step = momentul minim (luat in ordine inversa) din care oaia i poate fi luata de lup

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;

// parsare
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 maxStep = 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 (maxStep < v[i].step) {
            maxStep = v[i].step;
        }
    }

    // se inverseaza momentele
    ++maxStep; // pentru a fi nenule
    for (int i=1;i<=N;++i) {
        v[i].step = maxStep - v[i].step;
    }

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


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

    for (int j=1;j<=maxStep;++j) {
        for (int i=1;i<=N;++i) {

            // daca oaia i poate fi luata in momentul j
            bool available = (j>=v[i].step) ? 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;
            }
        }
    }

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