This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int N_ = 2005;
const ll INF = (ll)1e10;
int N;
ll Table[2][N_+N_+50];
#define tb(i, j) Table[(i) & 1][(j) + N_]
ll ans;
void maximize (ll &t, ll v) {
t = max(t, v);
}
int main() {
scanf("%d", &N);
for(int i = -N; i <= N; i++) tb(0, i) = -INF;
tb(0, 0) = 0;
int suma = 0;
for(int r = 1; r <= N; r++) {
int a, b; scanf("%d%d", &a, &b);
for(int i = -N; i <= N; i++) tb(r, i) = tb(r-1, i);
for(int x = -N; x <= N; x++) {
int y = x + (a - 1);
maximize(tb(r, y), tb(r - 1, x) + b);
}
}
for(int i = -1; i <= N; i++) ans = max(ans, tb(N, i));
printf("%lld\n", ans);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |