QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#734763 | #9475. Pangu and Stones | ggg | AC ✓ | 42ms | 14532kb | C++20 | 1.4kb | 2024-11-11 14:58:38 | 2024-11-11 14:58:40 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#pragma GCC optimize(2)
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
inline int read()
{
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
int n,m,l,r,k;
int a[N],sum[N];
int dp[105][105][105];
void solve()
{
while(cin>>n>>l>>r)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
dp[i][j][k]=1e18;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
dp[i][i][1]=0;
}
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
dp[i][j][len]=0;
for(int k=2;k<=len;k++)
{
for(int h=i;h<j;h++)
{
dp[i][j][k]=min(dp[i][j][k],dp[i][h][1]+dp[h+1][j][k-1]);
}
if(k>=l&&k<=r)dp[i][j][1]=min(dp[i][j][1],dp[i][j][k]+sum[j]-sum[i-1]);
}
}
}
if(dp[1][n][1]==1e18)cout<<"0\n";
else cout<<dp[1][n][1]<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
// cin>>t;
int t=1;
while(t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5748kb
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: 0
Accepted
time: 42ms
memory: 14532kb
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:
120446 66473 51039 85346 94828 7238 1564 8723 2852 15764 4266 8950 13004 1617 7620 5699 13659 922 6649 15773 3982 13002 12870 10934 2617 5941 3725 2246 6745 0 14698 10875 7909 9886 36014 4659 8894 0 8017 8860 10726 1144 4294 10730 4830 5373 10102 1623 12988 15216 900 11084 10326 8190 9628 1871 0 448...
result:
ok 105 lines