Submission #991561

#	Time	Username	Problem	Language	Result	Execution time	Memory
991561		rsinventor	Self Study (JOI22_ho_t2)	C++17	100 / 100	131 ms	11348 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector <ll> vll;
typedef vector<bool> vb;
typedef vector <string> vs;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef vector <pii> vpii;

#define all(a) (a).begin(), (a).end()
#define pb push_back
#define endl "\n"

ll n, m;
ll adds(ll mid, vll& a, vll& b) {
    ll sum = 0;
    for(int i = 0; i < a.size(); i++) {
        if(a[i]>b[i]) {
            ll class_cnt = 1 + ((mid - 1) / a[i]);
            if (class_cnt > m) {
                sum += 1 + ((mid - a[i] * m - 1) / b[i]) + m;
            } else {
                sum += class_cnt;
            }
        } else {
            sum += 1 + ((mid-1)/b[i]);
        }
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    vll a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vll b(n);
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }

    ll l = 0;
    ll r = pow(2, 64)-1;
    while(l<r) {
        ll mid = l + (r - l)/2;
        if(adds(mid, a, b)<=n*m) {
            l = mid+1;
        } else {
            r = mid;
        }
    }
    cout << l-1 << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'll adds(ll, vll&, vll&)':
Main.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0; i < a.size(); i++) {
      |                    ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < n; i++) {
      |                    ~~^~~
Main.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < n; i++) {
      |                    ~~^~~
Main.cpp:51:22: warning: overflow in conversion from '__gnu_cxx::__promote_2<int, int, double, double>::__type' {aka 'double'} to 'll' {aka 'long long unsigned int'} changes value from '1.8446744073709552e+19' to '18446744073709551615' [-Woverflow]
   51 |     ll r = pow(2, 64)-1;
      |            ~~~~~~~~~~^~

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