#843481 (C++14) No.2227 King Kraken's Attack

• 問題: No.2227 King Kraken's Attack
• ユーザー: t98slider
• 提出日時: 2023-02-24 22:18:06
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 5,270 bytes
• コンパイル時間: 1,748 ms
• コンパイル使用メモリ: 165,916 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-04-10 09:28:00
• 合計ジャッジ時間: 9,613 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	1 ms; 6,940 KB
testcase_02	AC	1 ms; 6,944 KB
testcase_03	AC	3 ms; 6,944 KB
testcase_04	WA	-
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,944 KB
testcase_08	AC	2 ms; 6,944 KB
testcase_09	AC	2 ms; 6,940 KB
testcase_10	AC	1 ms; 6,944 KB
testcase_11	AC	2 ms; 6,944 KB
testcase_12	AC	2 ms; 6,944 KB
testcase_13	AC	2 ms; 6,940 KB
testcase_14	AC	513 ms; 6,940 KB
testcase_15	AC	499 ms; 6,940 KB
testcase_16	AC	504 ms; 6,940 KB
testcase_17	AC	311 ms; 6,944 KB
testcase_18	AC	39 ms; 6,944 KB
testcase_19	AC	500 ms; 6,940 KB
testcase_20	AC	471 ms; 6,940 KB
testcase_21	AC	401 ms; 6,944 KB
testcase_22	AC	145 ms; 6,940 KB
testcase_23	AC	13 ms; 6,940 KB
testcase_24	AC	260 ms; 6,940 KB
testcase_25	AC	268 ms; 6,940 KB
testcase_26	AC	531 ms; 6,944 KB
testcase_27	AC	45 ms; 6,940 KB
testcase_28	AC	343 ms; 6,940 KB
testcase_29	AC	334 ms; 6,940 KB
testcase_30	AC	335 ms; 6,940 KB
testcase_31	AC	310 ms; 6,944 KB
testcase_32	AC	156 ms; 6,940 KB
testcase_33	AC	125 ms; 6,944 KB
testcase_34	AC	91 ms; 6,948 KB
testcase_35	AC	164 ms; 6,940 KB
testcase_36	AC	160 ms; 6,940 KB
testcase_37	AC	18 ms; 6,940 KB
testcase_38	AC	12 ms; 6,940 KB
testcase_39	AC	14 ms; 6,944 KB
testcase_40	AC	16 ms; 6,944 KB
testcase_41	AC	33 ms; 6,944 KB
testcase_42	AC	10 ms; 6,944 KB
testcase_43	AC	18 ms; 6,944 KB
testcase_44	AC	29 ms; 6,944 KB
testcase_45	AC	2 ms; 6,944 KB

ソースコード

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define codefor int test;cin>>test;while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define vector3d(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
using namespace std;
template<class T> using rpriority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> istream& operator>>(istream& is, vector<T>& vec) {for(T& x : vec)is >> x;return is;}
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) {if(vec.empty())return os;os << vec[0];for(auto it = vec.begin(); ++it!= vec.end();)os << ' ' << *it;return os;}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){cin >> head;in(tail...);}
void out(){cout << '\n';}
template<class T>void out(const T& a){cout << a << '\n';}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){cout << head << ' ';out(tail...);}
const int INF = 1 << 30;
const long long INF2 = 1ll << 60;
template<class T> void chmax(T &a,const T b){if(b>a)a=b;}
template<class T> void chmin(T &a,const T b){if(b<a)a=b;}


struct stable_int{
    long long v;
    stable_int() : v(0) {}
    stable_int(long long _v) : v(_v){}
    stable_int& operator++() {
        if(__builtin_add_overflow(v, 1, &v))v = std::numeric_limits<long long>::max();
        return *this;
    }
    stable_int& operator--() {
        if(__builtin_sub_overflow(v, 1, &v))v = std::numeric_limits<long long>::min();
        return *this;
    }
    stable_int operator++(int) {
        stable_int result = *this;
        ++*this;
        return result;
    }
    stable_int operator--(int) {
        stable_int result = *this;
        --*this;
        return result;
    }
    stable_int& operator+=(const stable_int& rhs) {
        if(__builtin_add_overflow(v, rhs.v, &v))v = std::numeric_limits<long long>::max();
        return *this;
    }
    stable_int& operator-=(const stable_int& rhs) {
        if(__builtin_sub_overflow(v, rhs.v, &v))v = std::numeric_limits<long long>::min();
        return *this;
    }
    stable_int& operator*=(const stable_int& rhs) {
        long long pre = v;
        if(__builtin_mul_overflow(v, rhs.v, &v)){
            v = (pre > 0) ^ (rhs.v > 0) ? std::numeric_limits<long long>::min()
                                        : std::numeric_limits<long long>::max();
        }
        return *this;
    }
    stable_int& operator/=(const stable_int& rhs) {
        v /= rhs.v;
        return *this ; 
    }
    stable_int operator+() const { return *this; }
    stable_int operator-() const { return stable_int() - *this; }
    friend stable_int operator+(const stable_int& lhs, const stable_int& rhs) {
        return stable_int(lhs) += rhs;
    }
    friend stable_int operator-(const stable_int& lhs, const stable_int& rhs) {
        return stable_int(lhs) -= rhs;
    }
    friend stable_int operator*(const stable_int& lhs, const stable_int& rhs) {
        return stable_int(lhs) *= rhs;
    }
    friend stable_int operator/(const stable_int& lhs, const stable_int& rhs) {
        return stable_int(lhs) /= rhs;
    }
    friend bool operator==(const stable_int& lhs, const stable_int& rhs) {
        return (lhs.v == rhs.v);
    }
    friend bool operator!=(const stable_int& lhs, const stable_int& rhs) {
        return (lhs.v != rhs.v);
    }
    friend bool operator<(const stable_int& lhs, const stable_int& rhs) {
        return (lhs.v < rhs.v);
    }
    friend bool operator<=(const stable_int& lhs, const stable_int& rhs) {
        return (lhs.v <= rhs.v);
    }
    friend bool operator>(const stable_int& lhs, const stable_int& rhs) {
        return (lhs.v > rhs.v);
    }
    friend bool operator>=(const stable_int& lhs, const stable_int& rhs) {
        return (lhs.v >= rhs.v);
    }
    friend istream& operator>>(istream& is,stable_int& rhs) noexcept {
        long long _v;
        rhs = stable_int{(is >> _v, _v)};
        return is;
    }
    friend ostream& operator << (ostream &os, const stable_int& rhs) noexcept {
        return os << rhs.v;
    }
};

using ll = stable_int;

int main(){
    //clock_t finish = clock() + CLOCKS_PER_SEC / 1000 * 1960;
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL(h, w, la, lb, ka, kb);
    ll v = h * w, S = la * lb, ans = 1ll << 60;
    for(ll i = 0; i <= h; i++){
        ll rem = v - ka * i;
        ll ng = 0, ok = v, mid;
        if(kb >= 1) ok = v / kb + 1;
        while(ng + 1 < ok){
            mid = (ok + ng) / 2;
            if(min(h, la * i) * min(w, lb * mid) + kb * mid >= rem) ok = mid;
            else ng = mid;
        }
        chmin(ans, i + ok);
    }
    for(ll i = 0; i <= w; i++){
        ll rem = v - kb * i;
        ll ng = 0, ok = v, mid;
        if(ka >= 1) ok = v / ka + 1;
        while(ng + 1 < ok){
            mid = (ok + ng) / 2;
            if(min(h, la * mid) * min(w, lb * i) + ka * mid >= rem) ok = mid;
            else ng = mid;
        }
        chmin(ans, i + ok);
    }
    out(ans);
}