competitive programming

Codeforces 864E Fire

Problem: Codeforces 864E Fire

Well, we may easily think of the \’Knapsack\’ problem at the first glimpse of this problem. Luckily, with small modification on the solution to the \’Knapsack\’ problem we can solve this problem.

Let\’s use dynamic programming. Let dp[i][j] be the max total value of the first i items we can rescue in first j seconds. And we easily get dp[i][j] = dp[i-1][j-t[i]] + p[i]. Notice that j has to be smaller than d[i], or we cannot save this item and of course, larger than or equal to t[i]. And when we calculate the dp for answer, we have to iterate items in increasing order of their d[i]. You can simply figure out that, since the final answer must be with the latest time, and value for later time depends on value for earlier time.

And with the well-known trick for \’Knapsack\’ problem we can only use one-dimensional array as our dp.

My code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

const int N=2010;
int n;
int t,d,p;
struct node {
    int t,d,p,id;
    bool operator<(const node& rhs) const {
        return d<rhs.d;
    }
};
vector<node> a;
int dp[N];
vector<int> vec[N];
int idx=0;

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d%d%d",&t,&d,&p);
        a.pb({t,d,p,i});
    }
    sort(a.begin(),a.end());
    int mx=0;
    for (int i=0;i<n;i++) {
        for (int j=a[i].d-1;j>=a[i].t;j--) {
            if (dp[j]<dp[j-a[i].t]+a[i].p) {
                dp[j]=dp[j-a[i].t]+a[i].p;
                vec[j]=vec[j-a[i].t];
                vec[j].pb(a[i].id);
            }
            if (mx<dp[j]) {
                idx=j;
                mx=dp[j];
            }
        }
    }
    printf("%d\n",mx);
    printf("%d\n",(int)vec[idx].size());
    for (int ele:vec[idx]) printf("%d ",ele);
    printf("\n");
}