Submission #25990697

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 FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 600100, MAXK = 60;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 600100, MAXK = 60;
//const ll MOD = 998244353;
//const ll MOD = 1e9+7;
const ll INF = 1e17;
//const ld PI = asin(1) * 2.0;

ll n;
ll k;
ll a[MAXN];
ll pref1[MAXN], pref2[MAXN];
ll cnt[MAXN];

int main()
{
    FAST_IO;

    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) pref1[a[i]]++;
    FOR(i, 1, n) pref2[a[i]] += a[i];

    FOR(i, 1, MAXN-1) pref1[i] += pref1[i-1];
    FOR(i, 1, MAXN-1) pref2[i] += pref2[i-1];

   // ll c = sqrt(MAXN);
    //ll c = 4;

    ll ans = 1;

    /*FOR(x, 2, c) {
        FOR(i, 1, n) {
            ll toAdd = a[i]%x;
            toAdd = (x - toAdd) % x;
            cnt[x] += toAdd;
        }

        //cout << " x = " << x << " cnt = " << cnt[x] << endl;
    }*/

    FOR(x, 1, MAXN-1) {
        ll lst = 0, cr = x;
        while (cr < MAXN) {
            //cout << "      x = " << x << "  cr = " << cr << " lst = " << lst << endl;
            //cout << "        pref1 " << pref1[cr] << " - " << pref1[lst] << endl;
            //cout << "        pref2 " << pref2[cr] << " - " << pref2[lst] << endl;

            cnt[x] += (pref1[cr] - pref1[lst]) * cr;
            cnt[x] -= pref2[cr] - pref2[lst];

            //cnt[x] += cn

            lst = cr;
            cr += x;
        }

       // if (x < 10)
        //cout << "  x = " << x << " cnt = " << cnt[x] << endl;
    }

    FOR(i, 1, MAXN-1) if (cnt[i] <= k) ans = i;

    if (cnt[MAXN-1] <= k) {
        ll rem = k - cnt[MAXN-1];
        ll times = rem / n;
        ans = ((ll)(MAXN-1)) + times;
        //cout << " times = " << times << endl;
    }

    cout << ans << "\n";

    return 0;
}

Submission Info

Judge Result