pedra filosofal.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1010

pair <int,int> pi[MAXN];
int dp[MAXN][3610];
int n;

int solve(int atual, int tempo){
    if(atual >= n)return 0;
    if(dp[atual][tempo] >= 0)return dp[atual][tempo];
    int davez = 0, prox = 0;
    prox = solve(atual+1,tempo);
    if(pi[atual].second >= tempo)
        davez = pi[atual].first - pi[atual].second + solve(atual+1,pi[atual].first);
    return dp[atual][tempo] = max(davez,prox);
}

int main(){
    scanf("%d", &n);
    memset(dp,-1,sizeof(dp));
    for(int p = 0; p < n; p++){
        int i,j;
        scanf("%d %d", &i, &j);
        pi[p].first = j, pi[p].second = i;
    }
    sort(pi,pi+n);
    printf("%d\n",solve(0,0));
    return 0;
}