#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10005;
struct Node{
int w;
int h;
};
Node a[N];
int b[N];
bool cmp(const Node &a,const Node &b){
if(a.h==b.h){
return a.w>b.w;
}
else{
return a.h>b.h;
}
}
int main(){
int n,x,y,ans,an,max,sum,ma,lt,tot_w;
lt = 0;
cin>>n>>x>>y;
memset(b,0,sizeof(b));
ma = 0;
tot_w=0;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].h;
tot_w+=a[i].w;
if(a[i].h>ma){
ma = a[i].h;
}
if(a[i].w>x||a[i].h>y){
lt=1;
}
}
if(lt==1){
cout<<"impossible"<<endl;
return 0;
}
sort(a+1,a+n+1,cmp);
/* for(int i=1;i<=n;i++){
cout<<a[i].h<<" "<<a[i].w<<endl;
}
*/
sum = 0;
max = 0;
an = 0;
ans = 1;
for(int i=1;i<=n;i++){
if(b[i]==1){
continue;
}
sum+=a[i].w;
if(sum>x){
sum = sum -a[i].w;
for(int j=i+1;j<=n;j++){
if(sum+a[j].w<=x&&b[j]!=1){
// cout<<"-1"<<endl;
sum += a[j].w;
if(a[j].h>max){
max = a[j].h;
}
b[j] = 1;
}
}
// cout<<sum-a[i].w<<endl;
sum = a[i].w;
// cout<<sum<<endl;
//ma = max;
an += max;
max = a[i].h;
ans++;
}
if(a[i].h>max){
max = a[i].h;
}
}
//cout<<an<<endl;
an+=max;
// cout<<an<<endl;
// cout<<ans<<" "<<an<<endl;
if(ans>2||an>y){
cout<<"impossible"<<endl;
}
else{
if(ans==1){
if(ma==y){
cout<<"-1"<<endl;
}
else{
cout<<an<<endl;
}
}
else{
cout<<ma<<endl;
}
}
return 0;
}
我的做法有什么地方没有考虑到 为什么总是差一点过,求大佬解答!
全部评论
(0) 回帖