Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int N;
- int K;
- int L;
- int fun[1001];
- int ks[2][20001];
- int dizzy[1001];
- int sack()
- {
- ks[0][0]=0;
- ks[0][fun[0]]= dizzy[0];
- int cur;
- int next;
- int d1;
- int d2;
- for(int i=0; i+1<N; i++)
- {
- cur=i%2;
- next= (i+1)%2;
- fill(ks[next],ks[next]+20001, 300001);
- for(int j=0; j<=20000; j++)
- {
- d2= j+fun[i+1];
- if(ks[cur][j]<300001)
- {
- ks[next][j]= min(max(ks[cur][j]-K,0), ks[next][j]);
- if(ks[cur][j]+dizzy[i+1]<=L)
- ks[next][d2]= min(ks[cur][j]+dizzy[i+1],ks[next][d2]);
- }
- }
- }
- for(int i=20000; i>=0; i--)
- if(ks[(N-1)%2][i]<300001)
- return i;
- return -1;
- }
- int main()
- {
- while(true)
- {
- cin>> N;
- cin>> K;
- cin>> L;
- if(N==0)
- break;
- fill(ks[0],ks[0]+20001,300001);
- for(int i=0; i<N; i++)
- { cin>> fun[i]; cin>> dizzy[i];}
- cout<< sack()<< endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement