QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590803#9129. Quotient SumMu_SilkWA 3ms3784kbC++20733b2024-09-26 11:36:582024-09-26 11:37:02

Judging History

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

  • [2024-09-26 15:38:30]
  • hack成功,自动添加数据
  • (/hack/908)
  • [2024-09-26 11:37:02]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3784kb
  • [2024-09-26 11:36:58]
  • 提交

answer

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

void solve(){
    int n;cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    vector<ll> dp(n);

    vector<int> p(2001);
    for(int i=1;i<n;i++){
        dp[i]=dp[i-1]+a[i]/a[i-1];
        for(int j=1;j<2001;j++){
            while(p[j]<i&&p[j]*(j+1)<=a[i])p[j]++;
            if(p[j]<i)dp[i]=min(dp[i],dp[p[j]]+a[i]/a[p[j]]);
        }
        // dp[i]=1e18;
        // for(int j=0;j<i;j++)dp[i]=min(dp[i],dp[j]+a[i]/a[j]);
    }
    cout<<dp[n-1];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=1;
    // cin>>n;
    while(n--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3572kb

input:

3
2 3 6

output:

3

result:

ok "3"

Test #2:

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

input:

2
15 4

output:

3

result:

ok "3"

Test #3:

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

input:

9
284791808 107902 13660981249408 4622332661 13405199 24590921 361 244448137 16077087227955422

output:

4580

result:

ok "4580"

Test #4:

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

input:

9
12 9 5 17 2 6 7 1 15

output:

6

result:

ok "6"

Test #5:

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

input:

10
19 13 18 11 20 16 6 8 17 3

output:

4

result:

ok "4"

Test #6:

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

input:

8
5 7 11 16 2 15 1 20

output:

7

result:

ok "7"

Test #7:

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

input:

10
13 2 19 11 15 9 16 5 12 1

output:

7

result:

ok "7"

Test #8:

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

input:

8
9 1 14 11 3 12 8 20

output:

7

result:

ok "7"

Test #9:

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

input:

4
4 6 20 3

output:

5

result:

ok "5"

Test #10:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

382
1495 1297 1197 976 1335 486 1850 992 1483 1269 1898 1593 237 1342 711 957 1992 1401 1413 206 917 1831 1444 698 1291 1987 231 1559 1119 1822 1790 471 736 496 1157 1886 1974 699 1702 321 325 758 683 1826 1051 95 632 456 1224 1590 1394 1854 1226 1963 1926 1819 989 34 980 371 535 807 1541 144 433 12...

output:

11

result:

ok "11"

Test #11:

score: -100
Wrong Answer
time: 2ms
memory: 3508kb

input:

317
1565 1374 387 1215 766 1670 862 673 1391 70 727 152 182 26 1111 1430 64 1318 349 994 780 1762 1993 552 715 1943 967 972 1039 646 617 1822 373 486 1863 1179 1840 1781 1963 220 773 671 126 613 719 1660 334 1851 65 707 1862 490 1466 1590 1717 1723 656 1526 1138 31 1976 1823 1335 1719 397 612 593 13...

output:

9

result:

wrong answer 1st words differ - expected: '8', found: '9'