fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4. ll d[2005];
  5. int main(){
  6. int n;cin>>n;
  7. vector<int> p;
  8. fill(d,d+2005,LLONG_MIN);
  9. d[0]=0;
  10. for(int i=0;i<n;i++){
  11. int a,b;cin>>a>>b;
  12. if(a==0&&b>0)p.push_back(b);
  13. else for(int j=2004;j>=0;j--)if(d[j]!=LLONG_MIN)d[min(2004,j+max(0,a-1))]=max(d[min(2004,j+max(0,a-1))],d[j]+b);
  14. }
  15. sort(p.rbegin(),p.rend());
  16. for(int i=1;i<p.size();i++)p[i]+=p[i-1];
  17. ll r=*max_element(d,d+2005);
  18. for(int i=0;i<min(2004,(int)p.size());i++)r=max(r,d[i]+p[i]);
  19. cout<<r<<"\n";
  20. }
Success #stdin #stdout 0.01s 5324KB
stdin
6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1
stdout
0