QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#650275#9475. Pangu and Stonesucup-team5071#WA 31ms3832kbC++201.1kb2024-10-18 14:24:132024-10-18 14:24:13

Judging History

This is the latest submission verdict.

  • [2024-10-18 14:24:13]
  • Judged
  • Verdict: WA
  • Time: 31ms
  • Memory: 3832kb
  • [2024-10-18 14:24:13]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long 
void gmin(int &x,int y){
    if(x==-1)x=y;
    else if(y<x)x=y;
};
int solve(int n,int L,int R,vector<int> a){
    vector<vector<int>> dp(n+1,vector<int>(n+1,-1));
    sort(a.begin()+1,a.end());
    auto sum=a;
    for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
    function<int(int,int)> dfs = [&](int x,int y){
        if(dp[x][y]!=-1)return dp[x][y];
        if(x==y){
            if(x>=L&&x<=R)return 0ll;
            else return -1ll;
        }
        for(int i=0;i<x;i++){
            for(int j=(x-i)*L;j<=min((x-i)*R,y-i);j++){
                int v=dfs(j,y-i);
                if(v!=-1)gmin(dp[x][y],dfs(j,y-i)+sum[y-i]);
            }
        }
        // cout<<"x="<<x<<" y="<<y<<" dp="<<dp[x][y]<<endl;
        return dp[x][y];
    };
    int v=dfs(1,n);
    if(v==-1)return 0;
    else return v;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,L,R;
    while(cin>>n>>L>>R){
        vector<int> a(n+1);
        for(int i=1;i<=n;i++)cin>>a[i];
        cout<<solve(n,L,R,a)<<"\n";
    }
}

详细

Test #1:

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

input:

3 2 2
1 2 3
3 2 3
1 2 3
4 3 3
1 2 3 4

output:

9
6
0

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 31ms
memory: 3720kb

input:

100 4 7
570 608 194 26 243 470 418 119 1000 936 440 302 797 155 676 283 869 60 959 793 158 397 808 656 379 316 485 854 753 280 543 435 756 822 106 561 402 347 99 739 8 682 834 549 812 32 338 765 699 575 575 785 171 504 335 113 284 612 276 518 835 677 865 900 687 48 859 179 343 318 626 812 523 11 400...

output:

116415
56024
48257
79800
93274
7238
1564
8573
2852
15058
3805
7597
12558
1617
6551
5386
12586
922
5911
15460
3352
12154
11949
9790
2617
5851
3725
2246
6436
0
13759
10875
7909
9686
35116
4659
8681
0
8017
7461
9884
1144
4294
10228
4405
4788
10441
1623
11464
14811
900
11084
9987
7582
9488
1871
0
4084
3...

result:

wrong answer 1st lines differ - expected: '120446', found: '116415'