QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#665897#9475. Pangu and StonesHQLFWA 5ms35372kbC++202.0kb2024-10-22 15:46:202024-10-22 15:46:38

Judging History

This is the latest submission verdict.

  • [2024-10-22 15:46:38]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 35372kb
  • [2024-10-22 15:46:20]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ldb=long double;
using ull=unsigned long long;
const long long inf=0x3f3f3f3f3f3f3f3f;
using i128=__int128;
const int mod=1000000007;
const long double eps=0.00000000001;


ll dp[200][200][200];
void solve()
{
    ll n,l,r;
    while(cin>>n>>l>>r)
    {
        ll a[n+10];
        for(ll i=1;i<=n;i++)cin>>a[i];
        ll pre[n+10];
        ll lst[n+10];
        pre[0]=0;
        lst[n+1]=0;
        for(ll i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
        for(ll i=n;i>=1;i--)lst[i]=lst[i+1]+a[i];
        for(ll i=0;i<=n;i++)
        {
            for(ll j=0;j<=n;j++)
            {
                for(ll k=0;k<=n;k++)
                {
                    dp[i][j][k]=inf;
                }
            }
        }
        for(ll i=0;i<=n;i++)
        {
            for(ll j=0;j<=n;j++)
            {
                dp[0][i][j]=0;
            }
        }


        for(ll len=1;len<=n;len++)
        {
            for(ll i=1;i+len-1<=n;i++)
            {
                ll j=i+len-1;
                if(len<l)dp[len][i][j]=inf;
                else if(len>=l&&len<=r)dp[len][i][j]=pre[j]-pre[i-1];
                else if(len>r)
                {
                    for(ll tlen=max(len-r+1,l);tlen<=min(len-l+1,r);tlen++)
                    {
                        for(ll ti=i;ti+tlen-1<=j;ti++)
                        {
                            ll tj=ti+tlen-1;
                            dp[len][i][j]=min(dp[len][i][j],dp[tlen][ti][tj]*2+(pre[ti-1]-pre[i-1])+(lst[tj+1]-lst[j+1]));
                        }
                    }
                }
            }
        }

        ll ans=dp[n][1][n];
        if(ans==inf)
        {
            printf("0\n");
        }
        else
        {
            printf("%lld\n",ans);
        }
    }




}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5ms
memory: 35372kb

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:

0
66473
52318
0
0
7238
1564
0
2852
0
4266
8950
13004
1617
7620
5699
0
922
6649
0
3982
0
12870
10934
2617
5941
3725
2246
6745
0
14698
10875
7909
0
0
4659
8894
0
8017
8860
10726
1144
4294
0
4830
0
0
1623
13680
0
900
11084
10326
0
9628
1871
0
4489
3174
5715
1824
0
0
0
14127
5899
0
2708
1439
1474
0
0
29...

result:

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