QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#48509#3997. Candy Machinepaekae#AC ✓212ms7600kbC++1.1kb2022-09-14 13:22:452022-09-14 13:22:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-14 13:22:46]
  • 评测
  • 测评结果:AC
  • 用时:212ms
  • 内存:7600kb
  • [2022-09-14 13:22:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

std::mt19937 rng(std::random_device{}());
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;
typedef const ll& cll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

#define ls (loc<<1)
#define rs ((loc<<1)|1)

const int mod = 1e9+7;
const int inf_int = 0x7fffffff;
const int hf_int = 0x3f3f3f3f;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int n;
int a[1000100];

bool solve(cint T) {
    cin >> n;
    for(int i=1; i<=n; i++) { cin >> a[i]; }
    sort(a+1, a+1+n);
    int l=0;
    ll sum = 0;
    int ans = 0;
    for(int i=1; i<=n; i++) {
        sum += a[i];
        while(l <= i && 1ll*a[l]*i <= sum) { ++l; }
        ans = max(ans, i-l+1);
    }
    cout << ans << '\n';
    return true;
}

int main() {
    //freopen("1.in", "r", stdin);
    //cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T_=1;
    // std::cin >> T_;
    for(int _T=1; _T<=T_; _T++) { if(solve(_T) == 0) { break; } }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3644kb

input:

5
1 2 3 4 5

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

18
3 5 5 1 2 2 3 9 2 2 7 1 7 3 2 3 6 6

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

20
170421784 139902913 635488787 31946330 289281525 541340761 264115901 680775011 102068389 128171044 636359374 477042327 879154459 716982403 654668380 256334408 874949295 737194459 663371810 549070350

output:

12

result:

ok single line: '12'

Test #4:

score: 0
Accepted
time: 92ms
memory: 7524kb

input:

1000000
97 83 13 77 44 47 43 74 81 97 76 62 55 12 85 74 75 59 45 81 1 36 26 28 32 64 72 100 78 52 60 31 81 48 78 91 68 2 35 45 98 51 48 99 74 7 13 43 22 4 68 62 29 31 11 66 77 63 1 64 61 72 74 26 91 37 86 50 91 6 18 69 87 87 51 62 61 59 29 69 20 2 70 84 31 56 12 21 9 48 2 61 11 21 8 38 17 28 78 87 3...

output:

500717

result:

ok single line: '500717'

Test #5:

score: 0
Accepted
time: 160ms
memory: 7456kb

input:

1000000
145493 170549 915888 2504 680394 758139 24665 365499 242644 535590 994789 297247 518365 834337 852392 945750 480961 126953 485671 11673 262033 473744 199902 743475 91856 394619 779195 616388 60537 756645 570144 510464 285494 932570 298148 627373 110058 469501 686867 559208 82153 90754 231338...

output:

500373

result:

ok single line: '500373'

Test #6:

score: 0
Accepted
time: 212ms
memory: 7524kb

input:

999999
138842067 7483867 621306163 351281546 595944065 95480114 365508036 751387459 56035370 757174318 169438287 638944328 172990655 762444787 884150457 284572671 788442934 321169997 239880233 764811445 554749447 207350825 203005320 577205786 687656367 676361754 130565640 256253378 854937392 1229058...

output:

500117

result:

ok single line: '500117'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

18
1 1 1 1 1 1 1 1 1 1 1 1 7 3 2 3 6 6

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3480kb

input:

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 80 30 72 59 18

output:

5

result:

ok single line: '5'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

20
1 3 6 3 4 10 7 7 7 4 4 2 4 3 6 671 623 686 378 833

output:

7

result:

ok single line: '7'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

20
421784 9902913 5488787 1946330 9281525 1340761 4115901 775011 2068389 8171044 6359374 7042327 9154459 6982403 4668380 256334408 874949295 737194459 663371810 549070350

output:

8

result:

ok single line: '8'

Test #11:

score: 0
Accepted
time: 62ms
memory: 7600kb

input:

1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

217886

result:

ok single line: '217886'

Test #12:

score: 0
Accepted
time: 69ms
memory: 7444kb

input:

999997
3 6 7 9 2 6 3 7 10 3 10 3 6 7 6 7 1 1 2 6 7 6 10 3 2 10 4 3 7 6 7 4 8 2 7 3 3 3 5 7 5 3 1 3 3 1 5 1 6 1 3 5 1 5 4 2 7 8 6 5 9 5 8 5 9 8 9 2 7 1 7 6 10 3 6 10 8 10 5 1 4 9 2 8 8 9 6 5 9 2 10 3 5 3 9 7 7 4 10 7 2 7 4 7 7 4 1 6 7 2 5 5 9 7 10 7 1 7 3 2 6 7 6 3 5 9 8 1 2 7 9 10 1 7 8 8 10 2 8 3 3...

output:

388666

result:

ok single line: '388666'

Test #13:

score: 0
Accepted
time: 111ms
memory: 7448kb

input:

1000000
9 67 96 77 59 78 12 23 58 91 75 72 29 44 78 84 37 72 14 26 49 23 50 75 32 88 95 99 67 22 91 80 65 77 67 61 81 80 64 56 55 49 45 92 79 70 71 55 45 8 76 69 47 35 85 80 34 31 92 50 10 54 11 15 89 60 95 72 56 45 49 40 2 30 85 67 75 92 6 30 50 16 55 92 83 69 5 100 74 54 98 57 30 25 8 64 3 1 8 10 ...

output:

379639

result:

ok single line: '379639'

Test #14:

score: 0
Accepted
time: 127ms
memory: 7540kb

input:

999999
568 641 588 298 716 97 415 41 656 157 506 194 549 185 671 825 836 780 722 17 367 307 636 505 358 766 779 34 123 241 527 987 215 36 63 326 410 612 786 688 287 432 783 20 77 804 693 233 71 417 515 23 805 987 801 231 489 810 781 224 219 386 184 498 310 331 310 527 816 169 586 893 598 69 751 357 ...

output:

376801

result:

ok single line: '376801'

Test #15:

score: 0
Accepted
time: 132ms
memory: 7592kb

input:

1000000
5493 549 5888 2504 394 8139 4665 5499 2644 5590 4789 7247 8365 4337 2392 5750 961 6953 5671 1673 2033 3744 9902 3475 1856 4619 9195 6388 537 6645 144 464 5494 2570 8148 7373 58 9501 6867 9208 2153 754 1338 8689 8347 9236 6892 6682 9948 3616 3583 3500 4863 7625 3104 5841 294 1922 2075 1899 38...

output:

376572

result:

ok single line: '376572'

Test #16:

score: 0
Accepted
time: 146ms
memory: 7384kb

input:

999997
76279 4645 25217 93052 24609 36849 86680 4205 19718 80321 88207 27274 78010 35830 69628 34950 58262 75156 84858 37687 81716 71334 49128 69402 54934 30199 82630 72044 6752 89689 18651 46514 9945 47362 5713 59506 76494 65323 76503 1240 95727 73584 2270 35986 84272 64754 61 56308 94858 20664 363...

output:

377135

result:

ok single line: '377135'

Test #17:

score: 0
Accepted
time: 173ms
memory: 7524kb

input:

999997
173379 115754 515614 404626 265354 709587 812433 710386 299151 905092 8260 850091 756458 327551 828554 952266 103243 962298 854219 359057 551857 301600 779394 734195 420788 425615 842688 74458 12860 881498 41128 405794 944583 701448 339761 169051 1383 689107 410023 891914 146754 556139 968747...

output:

376532

result:

ok single line: '376532'

Test #18:

score: 0
Accepted
time: 142ms
memory: 7456kb

input:

999999
8842067 7483867 1306163 1281546 5944065 5480114 5508036 1387459 6035370 7174318 9438287 8944328 2990655 2444787 4150457 4572671 8442934 1169997 9880233 4811445 4749447 7350825 3005320 7205786 7656367 6361754 565640 6253378 4937392 2905813 6977178 9062949 3359375 4809013 5963382 6811295 939720...

output:

376742

result:

ok single line: '376742'