[TIOJ]1604. 蚯蚓之寄生蟲問題

題目連結：http://tioj.ck.tp.edu.tw/problems/1604

把時間排序然後dp。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
struct Node{
    lld id,st,w;
    bool operator<(const Node &x)const{
        return w < x.w;
    }
};
vector<Node> w;
vector<lld> chu[1005];
lld dp[1005];
lld *p;
int main(){jizz
    fill(dp,dp+1005,-1);
    lld s,e,m,a,b;cin >> s >> e >> m >> a >> b;
    p = new lld[a+b+5];
    for(int i = 0 ; i < m ; i++){
        for(int j = 0 ; j < a+b ; j++){
            lld t;cin >> t;
            chu[i].PB(t);
            w.PB({i,j,t});
        }
    }
    bool t = 0;
    sort(w.begin(),w.end());
    for(Node i : w){
        if(i.w >= e)break;
        if(!t && i.w >= s)t = 1,dp[0] = 0;
        if(i.w >= s && ((i.id != 0 &&  i.st < a)||(i.id != m-1 && i.st >= a))){
            if(p[i.st] == -1)dp[i.id] = max(dp[i.id],-1LL);
            else dp[i.id] = max(dp[i.id],p[i.st]+chu[i.id][i.st]-chu[i.id + (i.st < a ? -1 : 1)][i.st]);
        }
        p[i.st] = dp[i.id];
    }
    cout << e-dp[0]-s << endl;
    return 0;
}