QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#354642 | #8281. Pangu and Stones | mc020207# | WA | 2ms | 8224kb | C++17 | 1.6kb | 2024-03-15 19:58:34 | 2024-03-15 19:58:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define wln putchar('\n')
template<class T1,class T2> void chkmin(T1 &x,T2 y){if(y<x)x=y;}
template<class T1,class T2> void chkmax(T1 &x,T2 y){if(y>x)x=y;}
const int N=105,INF=1000000007;
int n,l,r,a[N],s[N];
int f[N][N][N],g[N];
int main()
{
scanf("%d%d%d",&n,&l,&r);
For(i,1,n)scanf("%d",a+i);
sort(a+1,a+n+1,[](int x,int y){return x>y;});
For(i,1,n)s[i]=s[i-1]+a[i];
fill(g+1,g+n+1,INF);
For(i,l,r)
Rof(j,n,i)
chkmin(g[j],g[j-i]+1);
// printf("g:");
// For(i,1,n)printf("%d ",g[i]);
// wln;
For(i,0,n-1)
For(j,1,n)
fill(f[i][j]+1,f[i][j]+n+1,INF);
f[0][1][1]=0;
For(i,0,n-1)
For(j,1,n)
For(k,1,j)
if(f[i][j][k]<INF)
For(ii,1,n)
if(g[ii]<=k&&j-g[ii]+ii<=n)
{
// printf("i=%d,j=%d,k=%d,ii=%d,g=%d,x=%d,y=%d\n",i,j,k,ii,g[ii],s[j]-s[j-g[ii]],s[ii]-s[j-g[ii]]);
chkmin(f[i+1][j-g[ii]+ii][ii],f[i][j][k]-i*(s[j]-s[j-g[ii]])+(i+1)*(s[j-g[ii]+ii]-s[j-g[ii]]));
}
// For(i,0,n-1)
// For(j,1,n)
// For(k,1,j)
// if(f[i][j][k]<INF)printf("f[%d][%d][%d]=%d\n",i,j,k,f[i][j][k]);
int ans=INF;
For(i,0,n-1)
For(k,1,n)
chkmin(ans,f[i][n][k]);
if(ans<INF)printf("%d\n",ans);
else printf("0\n");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3936kb
input:
3 2 2 1 2 3
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3928kb
input:
3 2 3 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
4 3 3 1 2 3 4
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 8224kb
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:
158692
result:
wrong answer 1st numbers differ - expected: '120446', found: '158692'