QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665858 | #9475. Pangu and Stones | HQLF | WA | 0ms | 3856kb | C++20 | 1.8kb | 2024-10-22 15:35:52 | 2024-10-22 15:36:01 |
Judging History
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: ''