QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#590785	#9129. Quotient Sum	Mu_Silk	WA	0ms	3804kb	C++20	880b	2024-09-26 11:24:15	2024-09-26 11:24:16

Judging History

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

[2024-09-26 15:38:30]
hack成功，自动添加数据
(/hack/908)

[2024-09-26 11:24:16]
评测

测评结果：WA
用时：0ms
内存：3804kb

查看

[2024-09-26 11:24:15]
提交

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);
    for(int i=1;i<n;i++){
        int l=0,r=i-1;
        while(r>=l){
            int t=(r-l)/3;
            int m1=l+t,m2=r-t;
            ll v1=dp[m1]+a[i]/a[m1];
            ll v2=dp[m2]+a[i]/a[m2];
            if(v1>v2){
                dp[i]=v2;
                l=m1+1;
            }
            else{
                dp[i]=v1;
                r=m2-1;
            } 
        }
        // 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;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3476kb

input:

3
2 3 6

output:

result:

ok "3"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

2
15 4

output:

result:

ok "3"

Test #3:

score: 0

Accepted

time: 0ms

memory: 3776kb

input:

9
284791808 107902 13660981249408 4622332661 13405199 24590921 361 244448137 16077087227955422

output:

result:

ok "4580"

Test #4:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

9
12 9 5 17 2 6 7 1 15

output:

result:

ok "6"

Test #5:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

10
19 13 18 11 20 16 6 8 17 3

output:

result:

ok "4"

Test #6:

score: 0

Accepted

time: 0ms

memory: 3528kb

input:

8
5 7 11 16 2 15 1 20

output:

result:

ok "7"

Test #7:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

10
13 2 19 11 15 9 16 5 12 1

output:

result:

ok "7"

Test #8:

score: 0

Accepted

time: 0ms

memory: 3772kb

input:

8
9 1 14 11 3 12 8 20

output:

result:

ok "7"

Test #9:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

4
4 6 20 3

output:

result:

ok "5"

Test #10:

score: -100

Wrong Answer

time: 0ms

memory: 3656kb

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:

result:

wrong answer 1st words differ - expected: '11', found: '12'