提出 #58480067

---

ソースコード 拡げる

//yukicoder@cpp17

#include <iostream>
#include <iomanip>

#include <algorithm>

#include <cmath>
#include <cctype>
#include <climits>
#include <cassert>

#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>

#include <random>

#include <bitset>

#include <complex>

#include <utility>

#include <numeric>

#include <functional>


using namespace std;
using ll = long long;
using P = pair<ll,ll>;


const ll MOD = 998244353;
const ll MODx = 1000000007;
const int INF = (1<<30)-1;
const ll LINF = (1LL<<62LL)-1;
const double EPS = (1e-10);


P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};


template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }
 
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる

計算量は変わらないが楽できるシリーズ
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる
*/

/* comment outed because can cause bugs
__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
*/

struct d{
  long long a,p,b,q;
};

// to over c with A, what is min cost?
long long nf(d A, long long c){
  long long a = A.a, b = A.b, p = A.p, q = A.q;
  long long ans = min((c+a-1)/a * p, (c+b-1)/b*q);
  for(int i = 0; (c+a-1)/a >= i; i++){
    ans = min(ans, (i*p + max(0LL,(c-a*i+b-1))/b*q));
  }
  return ans;
}

//29 5935177 2 487903 355232213
//72702279986499 72702278930352
long long f(d A, long long c){
  long long a = A.a, b = A.b, p = A.p, q = A.q;
  long long ans = min((c+a-1)/a * p, (c+b-1)/b*q);
  if(c/a < b){
    for(long long i = 0; (c+a-1)/a >= i; i++){ // i = len(S)
      if((c-a*i+b-1) < 0)break;
      ans = min(ans, (i*p + (c-a*i+b-1)/b*q));
    }
  }else{
    for(long long i = 0; b >= i; i++){
      if((c-a*i+b-1) < 0)break;
      ans = min(ans, (i*p + (c-a*i+b-1)/b*q));
    }
  }
  if(c/b < a){
    for(long long i = 0; (c+b-1)/b >= i; i++){ // i = len(S)
      if((c-b*i+a-1) < 0)break;
      ans = min(ans, (i*q + (c-b*i+a-1)/a*p));
    }
  }else{
    for(long long i = 0; a >= i; i++){
      if((c-b*i+a-1) < 0)break;
      ans = min(ans, (i*q + (c-b*i+a-1)/a*p));
    }
  }
  //cout << c << ":" << ans << endl;
  return ans;
}

void test(){
  random_device seed;
  mt19937 engine(seed());
  uniform_int_distribution<int> A(1, 100);
  uniform_int_distribution<int> B(1, 100);
  uniform_int_distribution<int> P(1, 10000000);
  uniform_int_distribution<int> Q(1, 10000000);
  uniform_int_distribution<int> C(1, 1000000000);
  int count = 0;
  while(true){
    int a = A(engine);
    int b = B(engine);
    int p = P(engine);
    int q = Q(engine);
    int c = C(engine);
    if(f({a,p,b,q},c) != nf({a,p,b,q},c)){
      cout << "ng" << endl;
      cout << a << " " << p << " " << b << " " << q << " " << c << endl;
      cout << f({a,p,b,q},c) << " " << nf({a,p,b,q},c) << endl;
      return;
    }else{
      cout << "ok" << count++ << endl;
      cout << a << " " << p << " " << b << " " << q << " " << c << endl;
      cout << f({a,p,b,q},c) << " " << nf({a,p,b,q},c) << endl;
    }
  }

}

int main(){
  //cout << f({29, 5935177, 2, 487903}, 355232213) << " " << nf({29, 5935177, 2, 487903}, 355232213) << endl;
  //return 0;
  //test();
  //return 0;
  int n,x;cin>>n>>x;
  vector<d> A(n);
  for(int i = 0; n > i; i++){
    cin>>A[i].a>>A[i].p>>A[i].b>>A[i].q;
  }
  long long mn = 0;
  long long mx = 1000001000;
  while(mx-mn > 1){
    long long ce = (mn+mx)/2;
    long long cost = 0;
    for(int i = 0; n > i; i++){
      cost += f(A[i], ce);
    }
    if(cost > x){
      mx = ce;
    }else{
      mn = ce;
    }
  }
  cout << mn << endl;
  return 0;
}

提出情報

ジャッジ結果