QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #470890 | #6397. Master of Both III | UESTC_xxx# | WA | 1ms | 5936kb | C++20 | 935b | 2024-07-10 16:50:00 | 2024-07-10 16:50:00 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
int n;
ll w[50005],d[25][25],f[500005],ans,mod=998244353;
vector<int>e[50005];
int main(){
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%lld",&w[i]);
for(int j=0;j<n;++j){
d[j][(j+i)%n]=w[i];
}
}
for(int k=0;k<n;++k)
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(int i=1;i<(1<<n);++i) f[i]=1e18;
for(ll i=0;i<(1<<(n-1));++i){
for(int j=1;j<n;++j){
if((1<<(j-1))&i){
f[i]=min(f[i],f[i^(1<<(j-1))]+d[j][0]);
for(int k=1;k<n;++k){
if(((1<<(k-1))&i)&&j!=k){
f[i]=min(f[i],f[i^(1<<(j-1))]+d[j][k]);
}
}
}
}
ans=(ans+(f[i]%mod)*((i*2+i*2+1)%mod))%mod;
}
printf("%lld",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3708kb
input:
3 2 1 2
output:
45
result:
ok 1 number(s): "45"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
4 1919810 999999998 999999997 114114514
output:
152175989
result:
ok 1 number(s): "152175989"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5932kb
input:
3 842160586 705327547 868243944
output:
78597628
result:
ok 1 number(s): "78597628"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5912kb
input:
5 198327434 147392532 760837755 771109105 676721155
output:
751568230
result:
ok 1 number(s): "751568230"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 5936kb
input:
10 831766351 33417723 223739726 80131988 348810263 415437931 119999060 799356097 512022962 23197703
output:
458771697
result:
wrong answer 1st numbers differ - expected: '308170104', found: '458771697'