28 D Don't fear, DravDe is kind

問題

制約条件

方針

ソースコード

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":" ");
}