弘文了

Subtask 0 太水了 我的算法（略有复杂）甚至没有实现排序竟然都过了。。。

一个Subtask调了老子快一个小时，直接就弘文了

原代码：

#include <bits/stdc++.h>
#define F(i,l,r) for(int i=(l);i<=(r);i++)
#define FF(i,r,l) for(int i=(r);i>=(l);i--)
#define ll long long
#define M 3205
using namespace std;

int n,m;
int pos[M];
int v[M][4];
int w[M][4];
int dp[M][4];
bool b[M];
struct node{
    int u,v,w;
    bool operator<(const node &x)const{
        return w<x.w;
    }
}a[M];
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;n/=10;
    F(i,1,m){
        cin>>a[i].u>>a[i].v>>a[i].w;
    }
    F(i,1,m){
        int x=a[i].u,y=a[i].v,z=a[i].w;
        x/=10;if(z==0){v[i][0]=x*y;w[i][0]=x;b[i]=1;}
        else{
            v[z][++pos[z]]=v[z][0]+x*y;w[z][pos[z]]=w[z][0]+x;
            if(pos[z]==2){v[z][3]=v[z][1]+v[z][2]-v[z][0];w[z][3]=w[z][1]+w[z][2]-w[z][0];pos[z]++;}
        }
    }
    F(i,1,m){
        if(!b[i])continue;
        FF(j,n,0){
            for(int k=0;k<=pos[i]&&w[i][k]<=j;k++){
//                if(!dp[j-w[i][k]][0]&&w[i][k]!=j)continue;
                dp[j][k]=max(dp[j][0],dp[j-w[i][k]][0]+v[i][k]);
                dp[j][0]=max(dp[j][0],dp[j][k]);
            }
        }
    }
    cout<<dp[n][0]*10<<'\n';

    return 0;
}

现代码：

#include <bits/stdc++.h>
#define F(i,l,r) for(int i=(l);i<=(r);i++)
#define FF(i,r,l) for(int i=(r);i>=(l);i--)
#define ll long long
#define M 3205
using namespace std;

int n,m;
int pos[M];
int v[M][4];
int w[M][4];
int dp[M][4];
int id[M];
bool b[M];
int ans;
struct node{
    int u,v,w,p;
    bool operator<(const node &x)const{
        return w<x.w;
    }
}a[M];
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;n/=10;
    F(i,1,m){
        cin>>a[i].u>>a[i].v>>a[i].w;a[i].p=i;
    }sort(a+1,a+1+m);
    F(i,1,m){
        int x=a[i].u,y=a[i].v,z=a[i].w;id[a[i].p]=i;
 //       cout<<x<<' '<<y<<' '<<z<<'\n';
        x/=10;if(z==0){v[i][0]=x*y;w[i][0]=x;b[i]=1;}
        else{
            z=id[z];
            v[z][++pos[z]]=v[z][0]+x*y;w[z][pos[z]]=w[z][0]+x;
            if(pos[z]==2){v[z][3]=v[z][1]+v[z][2]-v[z][0];w[z][3]=w[z][1]+w[z][2]-w[z][0];pos[z]++;}
        }
    }
    F(i,1,m){
        if(!b[i])continue;
        FF(j,n,0){
            for(int k=0;k<=pos[i];k++){
 //               if(!dp[j-w[i][k]][0]&&w[i][k]!=j)continue;
 //               cout<<v[i][k]<<' '<<w[i][k]<<"\n\n";
                if(w[i][k]>j)continue;
                dp[j][k]=max(dp[j][0],dp[j-w[i][k]][0]+v[i][k]);
                dp[j][0]=max(dp[j][0],dp[j][k]);
            }
        }
    }
    // cout<<'\n';F(i,1,n){
    //     dp[n][0]=max(dp[n][0],dp[i][0]);
    //     cout<<dp[i][0]<<'\n';
    // }cout<<'\n';
    cout<<dp[n][0]*10<<'\n';

    return 0;
}

这么个致命错误都没卡掉

优秀的CCF数据