Submission #61900445

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for (ll i = 0; i < n; ++i) cin >> a[i];
    ull l = 0, r = 1LL << 60;
    while (r - l > 1) {
        ull mid = (r + l) / 2;
        ull c = 0;
        bool overflow = false;
        for (ll i = 0; i < n; ++i) {
            ull x = (mid / a[i] + 1) / 2;
            if (x > (1LL << 30)) { // 2^30を超えるとオーバーフローの可能性
                overflow = true;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for (ll i = 0; i < n; ++i) cin >> a[i];

    ull l = 0, r = 1LL << 60;
    while (r - l > 1) {
        ull mid = (r + l) / 2;
        ull c = 0;
        bool overflow = false;

        for (ll i = 0; i < n; ++i) {
            ull x = (mid / a[i] + 1) / 2;
            if (x > (1LL << 30)) { // 2^30を超えるとオーバーフローの可能性
                overflow = true;
                break;
            }
            ull temp = x * x;
            if (temp > ULLONG_MAX / a[i]) { // オーバーフロー検出
                overflow = true;
                break;
            }
            c += temp * a[i];
            if (c >= m) break; // これ以上計算する必要はない
        }

        if (overflow || c >= m) r = mid;
        else l = mid;
    }

    ull res = 0, cost = 0;
    for (ll i = 0; i < n; ++i) {
        ull x = (l / a[i] + 1) / 2;
        res += x;

        if (x > 0) {
            ull temp = x * x;
            if (temp > ULLONG_MAX / a[i]) continue; // オーバーフローなら無視
            cost += temp * a[i];
        }
    }

    for (ll i = 0; i < n; ++i) {
        ull x = ((l + 1) / a[i] + 1) / 2;
        if (x > 0 && l + 1 == (2 * x - 1) * a[i]) {
            ull temp = (2 * x - 1) * a[i];
            if (cost + temp <= m) {
                res++;
                cost += temp;
            }
        }
    }

    cout << res << endl;
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:30:19: warning: comparison of integer expressions of different signedness: ‘ull’ {aka ‘long long unsigned int’} and ‘ll’ {aka ‘long long int’} [-Wsign-compare]
   30 |             if (c >= m) break; // これ以上計算する必要はない
      |                 ~~^~~~
Main.cpp:33:27: warning: comparison of integer expressions of different signedness: ‘ull’ {aka ‘long long unsigned int’} and ‘ll’ {aka ‘long long int’} [-Wsign-compare]
   33 |         if (overflow || c >= m) r = mid;
      |                         ~~^~~~
Main.cpp:53:29: warning: comparison of integer expressions of different signedness: ‘ull’ {aka ‘long long unsigned int’} and ‘ll’ {aka ‘long long int’} [-Wsign-compare]
   53 |             if (cost + temp <= m) {
      |                 ~~~~~~~~~~~~^~~~

Judge Result