QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #789250 | #9802. Light Up the Grid | wanghai673# | WA | 131ms | 12580kb | C++20 | 1.6kb | 2024-11-27 19:40:07 | 2024-11-27 19:40:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int T,a0,a1,a2,a3;
int f[20][1<<17];
void Min(int &x,int y)
{
if(y<x)x=y;
}
int main()
{
scanf("%d%d%d%d%d",&T,&a0,&a1,&a2,&a3);
int bt=(1<<16)-1;
for(int i=0;i<16;++i)
for(int j=0;j<=bt;++j)
f[i][j]=1e9;
f[15][0]=0;
for(int j=0;j<bt;++j)
for(int k=0;k<16;++k)
for(int i=0;i<16;++i)
{
int nw3=i^15;
Min(f[nw3][j|1<<nw3],f[i][j]+a3);
int nw2=i^5;
Min(f[nw2][j|1<<nw2],f[i][j]+a2);
nw2=i^10;
Min(f[nw2][j|1<<nw2],f[i][j]+a2);
int nw1=i^3;
Min(f[nw1][j|1<<nw1],f[i][j]+a1);
nw1=i^12;
Min(f[nw1][j|1<<nw1],f[i][j]+a1);
int nw0=i^1;
Min(f[nw0][j|1<<nw0],f[i][j]+a0);
nw0=i^2;
Min(f[nw0][j|1<<nw0],f[i][j]+a0);
nw0=i^4;
Min(f[nw0][j|1<<nw0],f[i][j]+a0);
nw0=i^8;
Min(f[nw0][j|1<<nw0],f[i][j]+a0);
}
for(int i=0;i<16;++i)
{
for(int j=bt;j;--j)
{
int nw=j^(j&-j);
Min(f[i][nw],f[i][j]);
}
}
while(T--)
{
int m;
scanf("%d",&m);
int st=0,ans=1e9;
while(m--)
{
int sm=0;
for(int i=3;~i;--i)
{
int x;
scanf("%1d",&x);
sm|=x<<i;
}
st|=1<<sm;
}
for(int i=0;i<16;++i)
Min(ans,f[i][st]);
printf("%d\n",ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 114ms
memory: 12580kb
input:
2 1000 100 10 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
1121 2
result:
ok 2 number(s): "1121 2"
Test #2:
score: 0
Accepted
time: 106ms
memory: 12340kb
input:
2 1 1 1 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
5 2
result:
ok 2 number(s): "5 2"
Test #3:
score: 0
Accepted
time: 110ms
memory: 12580kb
input:
1 1000000 1000000 1000000 1000000 1 11 11
output:
2000000
result:
ok 1 number(s): "2000000"
Test #4:
score: -100
Wrong Answer
time: 131ms
memory: 12464kb
input:
10000 8 2 7 8 8 00 01 00 11 00 10 11 11 10 10 01 10 01 00 10 11 8 11 01 11 00 01 10 11 11 00 01 01 01 01 00 11 10 9 00 00 01 01 10 11 00 01 11 10 11 00 11 11 00 11 01 10 9 11 11 10 00 11 00 11 01 00 10 01 11 00 01 01 01 10 01 11 00 01 01 01 10 10 00 11 11 11 11 10 ...
output:
38 32 39 39 40 36 42 38 44 41 39 44 38 41 37 32 29 42 39 44 38 39 48 41 29 37 41 42 34 34 32 49 34 36 41 43 52 37 37 34 29 36 47 48 46 35 48 37 41 42 53 33 44 41 39 41 47 53 45 38 46 46 41 33 38 38 45 37 42 44 34 39 28 34 32 41 36 43 42 37 44 38 34 38 34 34 46 44 48 38 47 40 37 40 45 29 36 44 39 34 ...
result:
wrong answer 1st numbers differ - expected: '34', found: '38'