建造堤坝

题目描述

在一个大型水利建设项目中，工程师们正在努力完成最后一段堤坝的建造。这段堤坝的完成需要至少体积为 $v$ 的混凝土。目前，工地上有 $n$ 批次不同规格的混凝土，每批次的体积和运输到堤坝现场所需的成本分别为 $k$ 和 $m$。由于工程已经进行了很长时间，预算有限，剩余的预算为 $c$。

输入格式

第一行是三个整数：$v,n,c$。

从第二行到第 $n+1$ 行分别为每批次混凝土的体积和运输到堤坝现场所需的成本。

输出格式

输出只有一行，如果工程师们能够完成堤坝的建造，则输出他们完成建造后剩下的最大预算，否则输出 Impossible （不带引号）。

样例 #1

样例输入 #1

100 2 10
50 5
50 5

样例输出 #1

0

样例 #2

样例输入 #2

10 2 1
50 5
10 2

样例输出 #2

Impossible

提示

数据范围及约定

• 对于 $20\%$ 的数据，$0<n \le 50$；
• 对于 $50\%$ 的数据，$0<n \le 1000$；
• 对于 $100\%$ 的数据，$0<n \le 10^4$，所有读入的数均属于 $[0,10^4]$，最后答案不大于 $c$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int v2,n,c,sum,mmin=10000000001;//c=背包容量 
int w[1000001],v[1000001];
int f[1000001];
bool isok=false;
int main(){
	cin>>v2>>n>>c;
	for(int i=1;i<=n;i++) {
		cin>>w[i]>>v[i];
		sum+=w[i];
		mmin=min(mmin,v[i]);
	}
	if(mmin>c || sum<v2) {
		cout<<"Impossible";
		isok=true;
	}
	for(int i=1;i<=n;i++){
		for(int j=v2;j>=w[i];j--){
			if(f[j-1]==0) f[j]=f[i-w[i]]+v[i];
			f[j]=max(f[i-1],f[i-w[i]]+v[i]);
		}
	}
	//if(sum<v2 || (c-f[v2])<0) cout<<"Impossible"<<endl;
	if(isok==true) return 0;
	else cout<<f[c];
	return 0;
}