Submission #26012713

Source Code Expand

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2021.09.20 20:00:34
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;


int main() {
    int n;ll k;cin >> n >> k;
    int maxA = 0;
    ll sumA = 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sumA += a[i];
        maxA = max(maxA,a[i]);
    }
    vector<int> cnt(maxA+1);
    for (int i = 0; i < n; i++) cnt[a[i]]++;
    for (int i = 0; i < maxA; i++) cnt[i+1] += cnt[i];
    if (sumA <= (k+sumA)/n) {
        cout << (k+sumA)/n << endl;
        return 0;
    }
    for (int g = maxA; g >= 1; g--) {
        ll total = -sumA;
        for (int k = 1; k <= (maxA+g-1)/g; k++) {
            total += (ll)(cnt[min(maxA,k*g)]-cnt[(k-1)*g])*k*g;
        }
        if (total > k) continue;
        cout << g << endl;
        return 0;
    }
    return 1;
}

Submission Info

Submission Time
Task C - Maximize GCD
User kanpurin
Language C++ (GCC 9.2.1)
Score 600
Code Size 918 Byte
Status AC
Exec Time 75 ms
Memory 5544 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 75
Set Name Test Cases
Sample 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt
All 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 02_large_ans_01.txt, 02_large_ans_02.txt, 02_large_ans_03.txt, 02_large_ans_04.txt, 02_large_ans_05.txt, 02_large_ans_06.txt, 02_large_ans_07.txt, 02_large_ans_08.txt, 02_large_ans_09.txt, 02_large_ans_10.txt, 03_rand_01.txt, 03_rand_02.txt, 03_rand_03.txt, 03_rand_04.txt, 03_rand_05.txt, 03_rand_06.txt, 03_rand_07.txt, 03_rand_08.txt, 03_rand_09.txt, 03_rand_10.txt, 03_rand_11.txt, 03_rand_12.txt, 03_rand_13.txt, 03_rand_14.txt, 03_rand_15.txt, 03_rand_16.txt, 03_rand_17.txt, 03_rand_18.txt, 03_rand_19.txt, 03_rand_20.txt, 03_rand_21.txt, 03_rand_22.txt, 03_rand_23.txt, 03_rand_24.txt, 03_rand_25.txt, 03_rand_26.txt, 03_rand_27.txt, 03_rand_28.txt, 03_rand_29.txt, 03_rand_30.txt, 03_rand_31.txt, 03_rand_32.txt, 03_rand_33.txt, 03_rand_34.txt, 03_rand_35.txt, 03_rand_36.txt, 03_rand_37.txt, 03_rand_38.txt, 03_rand_39.txt, 03_rand_40.txt, 04_small_ans_01.txt, 04_small_ans_02.txt, 04_small_ans_03.txt, 04_small_ans_04.txt, 04_small_ans_05.txt, 04_small_ans_06.txt, 04_small_ans_07.txt, 04_small_ans_08.txt, 04_small_ans_09.txt, 04_small_ans_10.txt, 04_small_ans_11.txt, 04_small_ans_12.txt, 04_small_ans_13.txt, 04_small_ans_14.txt, 04_small_ans_15.txt, 04_small_ans_16.txt, 04_small_ans_17.txt, 04_small_ans_18.txt, 04_small_ans_19.txt, 04_small_ans_20.txt, 05_handmade_01.txt, 05_handmade_02.txt
Case Name Status Exec Time Memory
01_sample_01.txt AC 6 ms 3424 KiB
01_sample_02.txt AC 2 ms 3548 KiB
01_sample_03.txt AC 2 ms 3540 KiB
02_large_ans_01.txt AC 42 ms 4784 KiB
02_large_ans_02.txt AC 35 ms 4780 KiB
02_large_ans_03.txt AC 31 ms 4600 KiB
02_large_ans_04.txt AC 37 ms 4772 KiB
02_large_ans_05.txt AC 45 ms 4868 KiB
02_large_ans_06.txt AC 44 ms 5048 KiB
02_large_ans_07.txt AC 67 ms 5408 KiB
02_large_ans_08.txt AC 66 ms 5544 KiB
02_large_ans_09.txt AC 14 ms 4432 KiB
02_large_ans_10.txt AC 15 ms 4476 KiB
03_rand_01.txt AC 40 ms 4596 KiB
03_rand_02.txt AC 36 ms 4844 KiB
03_rand_03.txt AC 20 ms 4336 KiB
03_rand_04.txt AC 27 ms 4524 KiB
03_rand_05.txt AC 28 ms 4680 KiB
03_rand_06.txt AC 29 ms 4740 KiB
03_rand_07.txt AC 31 ms 4672 KiB
03_rand_08.txt AC 29 ms 4680 KiB
03_rand_09.txt AC 24 ms 4676 KiB
03_rand_10.txt AC 35 ms 4616 KiB
03_rand_11.txt AC 18 ms 4476 KiB
03_rand_12.txt AC 23 ms 4412 KiB
03_rand_13.txt AC 60 ms 5148 KiB
03_rand_14.txt AC 58 ms 5144 KiB
03_rand_15.txt AC 16 ms 4476 KiB
03_rand_16.txt AC 23 ms 4480 KiB
03_rand_17.txt AC 44 ms 4944 KiB
03_rand_18.txt AC 44 ms 5040 KiB
03_rand_19.txt AC 25 ms 4784 KiB
03_rand_20.txt AC 24 ms 4680 KiB
03_rand_21.txt AC 44 ms 4960 KiB
03_rand_22.txt AC 42 ms 5104 KiB
03_rand_23.txt AC 64 ms 5200 KiB
03_rand_24.txt AC 64 ms 5272 KiB
03_rand_25.txt AC 48 ms 5044 KiB
03_rand_26.txt AC 48 ms 5004 KiB
03_rand_27.txt AC 34 ms 4752 KiB
03_rand_28.txt AC 30 ms 4680 KiB
03_rand_29.txt AC 27 ms 4488 KiB
03_rand_30.txt AC 26 ms 4352 KiB
03_rand_31.txt AC 58 ms 5224 KiB
03_rand_32.txt AC 59 ms 5312 KiB
03_rand_33.txt AC 34 ms 4692 KiB
03_rand_34.txt AC 30 ms 4840 KiB
03_rand_35.txt AC 19 ms 4344 KiB
03_rand_36.txt AC 21 ms 4580 KiB
03_rand_37.txt AC 32 ms 4788 KiB
03_rand_38.txt AC 31 ms 4664 KiB
03_rand_39.txt AC 61 ms 5372 KiB
03_rand_40.txt AC 62 ms 5128 KiB
04_small_ans_01.txt AC 39 ms 4600 KiB
04_small_ans_02.txt AC 33 ms 4780 KiB
04_small_ans_03.txt AC 42 ms 4608 KiB
04_small_ans_04.txt AC 39 ms 4744 KiB
04_small_ans_05.txt AC 30 ms 4604 KiB
04_small_ans_06.txt AC 37 ms 4600 KiB
04_small_ans_07.txt AC 33 ms 4744 KiB
04_small_ans_08.txt AC 33 ms 4680 KiB
04_small_ans_09.txt AC 54 ms 4920 KiB
04_small_ans_10.txt AC 56 ms 4880 KiB
04_small_ans_11.txt AC 48 ms 4956 KiB
04_small_ans_12.txt AC 41 ms 4872 KiB
04_small_ans_13.txt AC 59 ms 5124 KiB
04_small_ans_14.txt AC 57 ms 5276 KiB
04_small_ans_15.txt AC 51 ms 5108 KiB
04_small_ans_16.txt AC 58 ms 5008 KiB
04_small_ans_17.txt AC 31 ms 4392 KiB
04_small_ans_18.txt AC 33 ms 4476 KiB
04_small_ans_19.txt AC 67 ms 5308 KiB
04_small_ans_20.txt AC 66 ms 5372 KiB
05_handmade_01.txt AC 3 ms 4216 KiB
05_handmade_02.txt AC 75 ms 5536 KiB