連續背包

#include<bits/stdc++.h>
using namespace std;

const int N=105;
const int WL=10010;

int n,W;
int v[N],w[N];
long long dp[N][WL];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	
	cin>>n>>W;
	
	for(int i=1;i<=n;++i){
		cin>>w[i]>>v[i];
		w[i]+=w[i-1];
		v[i]+=v[i-1];
	}
	
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j){
			for(int k=0;k<=W;++k){
				if(k>=(w[i]-w[i-j])){
					dp[i][k]=max({
						dp[i][k],
						dp[i-j][k],
						dp[i-j][k-(w[i]-w[i-j])]+(v[i]-v[i-j])*j
					});
				}else{
					dp[i][k]=max(dp[i][k],dp[i-j][k]);
				}
			}
		}
	}
	
	long long mx=0;
	
	for(int i=1;i<=n;++i){
		for(int k=0;k<=W;++k){
			mx=max(mx,dp[i][k]);
		}
	}
	
	cout<<mx<<"\n";
}