QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#665858#9475. Pangu and StonesHQLFWA 0ms3856kbC++201.8kb2024-10-22 15:35:522024-10-22 15:36:01

Judging History

This is the latest submission verdict.

  • [2024-10-22 15:36:01]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3856kb
  • [2024-10-22 15:35:52]
  • 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;
    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,1ll);tlen<=max(len-l+1,1ll);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: 0
Wrong Answer
time: 0ms
memory: 3856kb

input:

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

output:

9

result:

wrong answer 2nd lines differ - expected: '6', found: ''