Submission #61818027

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;
#define endl '\n'
#define int long long
const int inf = 1e9;
void solve() {
    int n, m; cin >> n >> m;
    vector<int> p(n);
    for(int i = 0; i < n; ++i) cin >> p[i];
    auto ok = [&] (int x) {
        int res = 0;
        for(int i = 0; i < n; ++i) {
            int mx = (x / p[i] + 1) / 2;
            if(mx > inf) return false;
            mx *= mx;
            if(mx > m / p[i]) return false;
            if(res > m - mx * p[i]) return false;
            res += mx * p[i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

const int inf = 1e9;

void solve() {
    int n, m; cin >> n >> m;
    vector<int> p(n);
    for(int i = 0; i < n; ++i) cin >> p[i];

    auto ok = [&] (int x) {
        int res = 0;
        for(int i = 0; i < n; ++i) {
            int mx = (x / p[i] + 1) / 2;
            if(mx > inf) return false;
            mx *= mx;
            if(mx > m / p[i]) return false;
            if(res > m - mx * p[i]) return false;
            res += mx * p[i];
        }

        return res <= m;
    };

    int l = 0, r = m + 2;
    while(r - l > 1) {
        int mid = (r + l) >> 1;
        if(ok(mid)) l = mid;
        else r = mid;
    }

    int ans = 0;
    int nxt = 1e18;
    for(int i = 0; i < n; ++i) {
        int qt = (l / p[i] + 1) / 2;
        ans += qt;
        m -= qt * qt * p[i];
        nxt = min(nxt, (2*(qt + 1) - 1) * p[i]);
    }

    cout << ans + m / nxt;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

Submission Info

Judge Result