SXOI 2016 T1 bridge

//bridge #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; int n,W,ans=1e9; int yu[20],mx[20]; bool b[20]; struct person {int w,t;} p[20]; inline bool comp(const person &x,const person &y) { return x.t>y.t; } inline void dfs(int num,int now) { int i,j; if(now>=ans) return; if(num>n) { ans=now; return; } fo(i,1,num) if(p[num].w<=yu[i]) { yu[i]-=p[num].w; int tmp=mx[i]; if(p[num].t>mx[i]) mx[i]=p[num].t,dfs(num+1,now+p[num].t-tmp); else dfs(num+1,now); mx[i]=tmp; yu[i]+=p[num].w; } } int main() { int i,j,k; scanf("%d%d",&W,&n); fo(i,1,n) scanf("%d%d",&p[i].t,&p[i].w),yu[i]=W; sort(p+1,p+n+1,comp); dfs(1,0); printf("%d\n",ans); return 0; } /* 100 3 24 60 10 40 18 50 */