Cod sursa(job #2793272)

Utilizator bog_manBogdan Manghiuc bog_man Data 3 noiembrie 2021 13:28:08
Problema Lupul Urias si Rau Scor 44
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve(){
    ifstream in("lupu.in");
    ofstream out("lupu.out");
    
    int n, x, l;
    in >> n >> x >> l;
    
    vector<pair<int, int>> sheep(n);
    for (int i = 0; i < n; ++i){
        pair<int, int> p;
        in >> p.first >> p.second;
        sheep[i] = p;
    }
    
    sort(sheep.begin(), sheep.end(), 
        [](const pair<int, int> a, const pair<int, int> b) {
            return a.first < b.first;             
        }
    );
    
    vector<vector<ll>> dp (n, vector<ll> (n+1));
    
    for (int j = 0; j <= n; ++j){
        if (sheep[0].first + j * l > x)
            dp[0][j] = 0;
        else
            dp[0][j] = sheep[0].second;
    }
    
    for (int i = 1; i < n; ++i){
        for (int j = 0; j <= n; ++j){
            if (sheep[i].first + j * l > x)
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max (dp[i-1][j], sheep[i].second + dp[i-1][j+1]);
        }
    }
    
    out<< dp[n-1][0] << endl;
    
    in.close();
    out.close();
}

int main(){
    solve();
    return 0;
}