求调,WA on 43
查看原帖
求调,WA on 43
280999
_fairytale_楼主2023/12/27 11:59
#include<bits/stdc++.h>
#define re register
#define ll long long
#define printc cerr<<"-------------------------\n"
#define rep(x,a,b) for(re int (x)=(a);(x)<=(b);++(x))
using namespace std;
#define inf 0x3f3f3f3f3f3f3f3f
#define maxn 100010
int n,m;
ll ans,ansp;
struct cars{
	int v,c,l,r,pos;
}c[maxn];
vector<cars>vec[maxn];
int a[maxn],tot;
ll f[maxn];//f[i]表示考虑前i个数,且强制选i的最大价值
//f[i]=f[j](j<i,v[j].l+v[j].c=v[i].l)+v[i].v
map<ll,ll>mp;
int pre[maxn]; 
inline void wrk(vector<cars>& v){
	int sz=(int)v.size();
	mp.clear();
	mp[0]=sz;
	v.emplace_back(cars{0,0,0,0,0});
	rep(i,0,sz-1){
		if(!mp.count(v[i].l)){
			f[i]=-inf;
		}
		else{
			f[i]=f[mp[v[i].l]]+v[i].v;
			pre[v[i].pos]=v[mp[v[i].l]].pos;
			if(!mp.count(v[i].l+v[i].c)||f[mp[v[i].l+v[i].c]]<f[i]){
				mp[v[i].l+v[i].c]=i;                   
			}
		}
		if(v[i].r==0){
			if(f[i]>ans){
				ans=f[i];
				ansp=v[i].pos;
			}
		}
	}
}
int stac[maxn],top;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>n;
    rep(i,1,n){
    	c[i].pos=i;
    	cin>>c[i].v>>c[i].c>>c[i].l>>c[i].r;
    	a[++tot]=c[i].c+c[i].l+c[i].r;
	}
	stable_sort(a+1,a+tot+1);
	tot=unique(a+1,a+tot+1)-a-1;
	rep(i,1,n){
		vec[lower_bound(a+1,a+tot+1,c[i].c+c[i].l+c[i].r)-a].emplace_back(c[i]);
	}
	rep(i,1,n){
		wrk(vec[i]);
	}
	while(ansp){
		stac[++top]=ansp;
		ansp=pre[ansp];
	}
	cout<<top<<'\n';
	while(top){
		cout<<stac[top--]<<" ";
	}
	return 0;
}
2023/12/27 11:59
加载中...