問題
制約条件
方針
int n,v[100000],c[100000],l[100000],r[100000];
int prev[100000];
map<pi,int> dp,car;
void run(){
cin>>n;
rep(i,n)dp.clear();
rep(i,n)cin>>v[i]>>c[i]>>l[i]>>r[i], prev[i]=-1;
int ans=0,ansc=-1;
rep(i,n){
map<pi,int>::iterator j=dp.find(mp(l[i],r[i]+c[i]));
if(j!=dp.end()){
if(dp[mp(j->first.first+c[i],r[i])]<j->second+v[i]){
dp[mp(j->first.first+c[i],r[i])]=j->second+v[i],
car[mp(j->first.first+c[i],r[i])]=i,
prev[i]=car[mp(l[i],r[i]+c[i])];
if(r[i]==0&&ans<j->second+v[i])ans=j->second+v[i],ansc=i;
}
}
if(l[i]==0){
if(dp[mp(c[i],r[i])]<v[i]){
dp[mp(c[i],r[i])]=v[i],car[mp(c[i],r[i])]=i;
if(r[i]==0&&ans<v[i])ans=v[i],ansc=i;
}
}
}
vi v;
for(;ansc!=-1;ansc=prev[ansc])v.pb(ansc);
cout<<v.size()<<endl; reverse(all(v));
rep(i,v.size())cout<<v[i]+1<<(i==v.size()-1?"\n":" ");
}