60pts求调（玄关）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[105][105][2005][2];
int n,k,m;
struct node
{
    int w,t;
    bool operator <(const node &f) const
    {
        return t<f.t;
    }
};
int sum[1005][105];
vector<node> op[1005];
int id[1005],cnt=0;
int pal(int x,int t)
{
    int l=0,r=op[x].size()+1;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if(op[x][mid-1].t<t) r=mid;
        else l=mid;
    }
    return sum[x][l];
}
signed main()
{
//    freopen("go.in","r",stdin);
//    freopen("go.out","w",stdout);
    cin>>n>>k>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        op[x].push_back({y,z});
    }
    for(int i=1;i<=n;i++)
    {
        sort(op[i].begin(),op[i].end());
        if(op[i].size()>0) id[++cnt]=i;
        for(int j=1;j<=op[i].size();j++) sum[i][j]=sum[i][j-1]+op[i][j-1].w;
    }
    id[cnt+1]=1e18;
    int pos=0;
    for(int i=1;i<=cnt;i++)
    {
        if(id[i]==k)
        {
            pos=i;
            break;
        }
    }
    if(pos==0)
    {
        for(int i=0;i<=cnt;i++)
        {
            if(k>id[i]&&k<id[i+1])
            {
                for(int j=cnt;j>=i+1;j--)
                {
                    id[j+1]=id[j];
                }
                id[i+1]=k;
                pos=i+1;
                break;
            }
        }
        cnt++;
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=i;j<=cnt;j++)
        {
            for(int k=1;k<=2000;k++) dp[i][j][k][0]=dp[i][j][k][1]=-1e18;
        }
    }
    dp[pos][pos][1][0]=dp[pos][pos][1][1]=sum[pos][op[id[pos]].size()];
    for(int k=2;k<=2000;k++)
    {
        for(int len=2;len<=cnt;len++)
        {
            for(int i=1;i<=cnt-len+1;i++)
            {
                int j=i+len-1;
                if(k>id[i+1]-id[i])dp[i][j][k][0]=max(dp[i][j][k][0],dp[i+1][j][k-(id[i+1]-id[i])][0]+pal(id[i],k+1));
                if(k>id[j]-id[i])dp[i][j][k][0]=max(dp[i][j][k][0],dp[i+1][j][k-(id[j]-id[i])][1]+pal(id[i],k+1));
                if(k>id[j]-id[i])dp[i][j][k][1]=max(dp[i][j][k][1],dp[i][j-1][k-(id[j]-id[i])][0]+pal(id[j],k+1));
                if(k>id[j]-id[j-1])dp[i][j][k][1]=max(dp[i][j][k][1],dp[i][j-1][k-(id[j]-id[j-1])][1]+pal(id[j],k+1));
            }
        }
    }
    int maxn=0;
    for(int i=2;i<=2000;i++) maxn=max(maxn,dp[1][cnt][i][0]),maxn=max(maxn,dp[1][cnt][i][1]);
    cout<<maxn;
    return 0;
}
/*
79 3 14
13 82 4
14 17 8
20 65 23
27 91 4
33 23 54
34 14 2
36 29 37
37 41 31
48 6 59
50 85 22
52 92 56
59 97 101
75 77 9
77 18 35

65+23+29+6+92+97
*/