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
15
1 -4034
1 3406
0 6062
4 -6824
0 9798
0 4500
0 -1915
1 2137
0 9786
0 7330
0 -9365
2 2730
0 -5797
0 6129
0 8925
stdout
43417