Submission #610613

#	Time	Username	Problem	Language	Result	Execution time	Memory
610613		ishmam8683	Self Study (JOI22_ho_t2)	C++14	100 / 100	303 ms	16172 KiB

Main

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <array>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <iomanip>
#include <cstring>
#include <string> // for getline
using namespace std;

#define endl "\n"
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define e emplace

template <typename T> istream& operator>>(istream &is, vector<T>& a) { for (auto& i : a) is >> i; return is; }
template <typename T> ostream& operator<<(ostream& os, vector<T>& a) { for (auto& i : a) os << i << " "; return os; };
// template <typename T> ostream& operator<<(ostream &os, const vector<T>& v) { os << '{'; string s; for (const auto &x : v) os << s << x, s = " "; return os << '}'; }
template <typename A, typename B> istream& operator>>(istream& is, pair<A, B>& i) { return is >> i.ff >> i.ss; }
template <typename A, typename B> ostream& operator<<(ostream& os, const pair<A, B>& i) { return os << i.ff << " " << i.ss; }
// template <typename A, typename B> ostream& operator<<(ostream& os, const pair<A, B>& i) { return os << '{' << i.ff << ", " << i.ss << '}'; }
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

using ll = long long;
using ld = long double;
using pii = pair<int, int>; using pli = pair<ll, int>; using pil = pair<int, ll>;
using pll = pair<ll, ll>;   using vl = vector<ll>;     using vvl = vector<vl>;
using vi = vector<int>;     using vb = vector<bool>;   using vc = vector<char>;
using vvi = vector<vi>;     using vvb = vector<vb>;    using vvc = vector<vc>;
using vpii = vector<pii>;   using vpll = vector<pll>;  using vs = vector<string>;
using tiii = tuple<int, int, int>; using vtiii = vector<tiii>;
template <class A, class B> using umap = unordered_map<A, B>;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bug cerr << "!Bugged..." << endl
#define add(x, y) (x + y >= MOD ? x + y - MOD : x + y)

const vs cq = { "NO", "YES"};
const int dx[8] = { -1,  0, 0, 1, 1,  1, -1, -1};
const int dy[8] = { 0, -1, 1, 0, 1, -1,  1, -1};
const int INF = 2147483647;
const ll LINF = 9223372036854775807;
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 1;

int main()
{
#ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // freopen("error.txt", "a", stderr);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    // cout.tie(NULL);

    int ttt(1);
    // cin >> ttt;
    for (int itt = 1; itt <= ttt; itt++)
    {
        ll n, m;
        cin >> n >> m;
        vl a(n); cin >> a;
        vl b(n); cin >> b;
        vl c(n);
        for (int i = 0; i < n; i++) {
            c[i] = max(a[i], b[i]);
        }

        ll l = 0, r = 1e18, ans;
        auto chk = [&](ll x) {
            ll days = n * m;
            vl cur(n, x); // c[i] * g >= x;
            for (int i = 0; i < n; ++i) {
                if (a[i] <= b[i]) continue;
                ll g = (x + c[i] - 1) / c[i];
                g = min(g, m);
                cur[i] -= c[i] * g;
                days -= g;
                if (days < 0) return false;
            }
            for (int i = 0; i < n; ++i) {
                if (cur[i] > 0) {
                    ll g = (cur[i] + b[i] - 1) / b[i];
                    days -= g;
                }
                if (days < 0) return false;
            }
            // debug(x, days);
            // debug(cur);
            return true;
        };
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (chk(mid)) l = mid + 1, ans = mid;
            else r = mid - 1;
        }
        cout << ans;

    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9