QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #782561 | #9802. Light Up the Grid | wallcrack# | WA | 323ms | 4224kb | C++20 | 2.5kb | 2024-11-25 20:29:16 | 2024-11-25 20:29:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a0,a1,a2,a3;
int f[16][512];
int cst[512];
int dp[(1<<16)+10];
void cal(int &u,int p)
{
if(p<4)
{
int now=(u>>p)&1;
if(now==0)
{
u+=1<<p;
}
else {
u-=1<<p;
}
}
else if(p<6)
{
if(p==4)
{
cal(u,0);
cal(u,1);
}
else if(p==5)
{
cal(u,2);
cal(u,3);
}
}
else if(p<8)
{
if(p==6)
{
cal(u,0);
cal(u,2);
}
else {
cal(u,1);
cal(u,3);
}
}
else {
cal(u,0);
cal(u,2);
cal(u,1);
cal(u,3);
}
return;
}
void init()
{
a1=min(a1,2*a0);
a2=min(a2,2*a0);
a3=min(a3,4*a0);
a3=min(a3,a1+a1);
a3=min(a3,a2+a2);
for(int j=1;j<(1<<9);j++)
{
int ans=0;
for(int k=0;k<9;k++)
{
if((j>>k)&1)
{
if(k<4)
{
ans+=a0;
}
else if(k<6)
{
ans+=a1;
}
else if(k<8)
{
ans+=a2;
}
else ans+=a3;
}
}
cst[j]=ans;
}
for(int i=0;i<16;i++)
{
for(int j=1;j<(1<<9);j++)
{
int ans=i;
for(int k=0;k<9;k++)
{
if((j>>k)&1)
{
cal(ans,k);
}
}
f[i][j]=ans;
}
}
}
int dfs(int i)
{
if(i==0)
{
return dp[i]=0;
}
if(dp[i])
{
return dp[i];
}
vector<int>tep;
for(int k=0;k<16;k++)
{
if((i>>k)&1)
{
for(int j=1;j<(1<<9);j++)
{
if(f[k][j]==15)
{
tep.push_back(j);
}
}
}
}
for(auto &v:tep)
{
int ans=0;
for(int k=0;k<15;k++)
{
if((i>>k)&1)
{
if(f[k][v]==15)
{
continue;
}
else {
ans+=1<<(f[k][v]);
}
}
}
if(dp[i]==0)
{
dp[i]=dfs(ans)+cst[v];
}
else {
dp[i]=min(dp[i],dfs(ans)+cst[v]);
}
}
if((i>>15)&1)
{
int ans=i;
ans-=1<<15;
int ctt=min({2*a0,2*a1,2*a2,2*a3});
if(dp[i]==0)
{
dp[i]=dfs(ans)+ctt;
}
else {
dp[i]=min(dp[i],dfs(ans)+ctt);
}
}
return dp[i];
}
void solve()
{
int m;
cin>>m;
int res=0;
string a,b;
for(int i=1;i<=m;i++)
{
int u=0;
cin>>a>>b;
if(a[0]=='1')
{
u+=1<<0;
}
if(a[1]=='1')
{
u+=1<<1;
}
if(b[0]=='1')
{
u+=1<<2;
}
if(b[1]=='1')
{
u+=1<<3;
}
res+=1<<u;
}
cout<<dfs(res)<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t>>a0>>a1>>a2>>a3;
init();
while(t--)
{
solve();
}
return 0;
}
/*
1 1000 100 10 1
1
11
11
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3716kb
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: 1ms
memory: 3904kb
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: 1ms
memory: 3680kb
input:
1 1000000 1000000 1000000 1000000 1 11 11
output:
2000000
result:
ok 1 number(s): "2000000"
Test #4:
score: -100
Wrong Answer
time: 323ms
memory: 4224kb
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:
32 30 34 34 40 36 41 38 40 37 34 42 34 37 37 31 29 35 39 40 38 36 40 34 25 34 34 38 34 31 32 37 34 36 37 40 40 34 37 34 29 35 35 36 42 35 35 34 38 34 37 29 38 38 36 37 43 36 41 30 40 39 33 33 34 36 34 34 42 40 34 32 28 34 32 37 34 39 34 37 32 36 30 30 32 34 38 40 34 36 40 39 34 36 34 25 36 40 36 34 ...
result:
wrong answer 1st numbers differ - expected: '34', found: '32'