PKU 3045 Cow Acrobats
http://poj.org/problem?id=3045
牛がn匹いる。
牛iは重さWi、強さSiを持っている。
この時に牛を積んでいくことを考える。
それぞれの牛の崩れ安さは、その牛の上にいる全ての牛の重さの合計から、その牛自信の強さを引いたものになる。
この時、崩れやすさの最も大きい牛が出来るだけ小さな値を持つような順番にしたときの、その牛の崩れ安さを求めろというような問題。
PKU 3262と似たように考える。
2匹の牛で上下関係を決めることができるので、ソートしてシミュレーションする。
最初ans=0にしてたら、WAをもらい、入力をcinでやったらTLEをもらいました。
sort関数の使い方を微妙に覚えました。
struct cmp{ bool operator()(const PI&l,const PI&r)const{ return l.F-r.S>r.F-l.S; } }; PI in[50000]; main(){ int n; cin>>n; ll sum=0; rep(i,n){ scanf("%d%d",&in[i].F,&in[i].S); sum+=in[i].F; } sort(in,in+n,cmp()); ll ans=-(1LL<<40); rep(i,n){ sum-=in[i].F; ans=max(ans,sum-in[i].S); } cout<<ans<<endl; }