QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#665897 | #9475. Pangu and Stones | HQLF | WA | 5ms | 35372kb | C++20 | 2.0kb | 2024-10-22 15:46:20 | 2024-10-22 15:46:38 |
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;
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;
}
詳細信息
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'