test/aoj/ALDS1_15_B.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 12:29:50+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_B

Depends on

• io/precision.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_B
// verification-helper: ERROR 1e-6

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

#define call_from_test
#include "../../io/precision.cpp"
#undef call_from_test

signed main(){
  using D = double;

  int n,w;
  cin>>n>>w;
  vector<D> vs(n),ws(n);
  for(int i=0;i<n;i++) cin>>vs[i]>>ws[i];

  using P = pair<D, int>;
  vector<P> vp;
  for(int i=0;i<n;i++)
    vp.emplace_back(vs[i]/ws[i],i);

  sort(vp.rbegin(),vp.rend());

  D ans=0,res=w;
  for(auto p:vp){
    D amount=min(ws[p.second],res);
    res-=amount;
    ans+=amount*p.first;
  }

  cout<<ans<<endl;
  return 0;
}

#line 1 "test/aoj/ALDS1_15_B.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_B
// verification-helper: ERROR 1e-6

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

#define call_from_test
#line 1 "io/precision.cpp"

#line 3 "io/precision.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/ALDS1_15_B.test.cpp"
#undef call_from_test

signed main(){
  using D = double;

  int n,w;
  cin>>n>>w;
  vector<D> vs(n),ws(n);
  for(int i=0;i<n;i++) cin>>vs[i]>>ws[i];

  using P = pair<D, int>;
  vector<P> vp;
  for(int i=0;i<n;i++)
    vp.emplace_back(vs[i]/ws[i],i);

  sort(vp.rbegin(),vp.rend());

  D ans=0,res=w;
  for(auto p:vp){
    D amount=min(ws[p.second],res);
    res-=amount;
    ans+=amount*p.first;
  }

  cout<<ans<<endl;
  return 0;
}

Back to top page