QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #408928 | #6539. Treasure Box | Doqe | WA | 21ms | 9768kb | C++17 | 1.1kb | 2024-05-11 12:15:52 | 2024-05-11 12:15:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int nd[N],V[N];
long long val[N];
char s[N];
int main()
{
int T;cin>>T;
while(T--)
{
int n,C,pl=0,pr=0;
cin>>n>>C>>s+1;
for(int i=1;i<=n;++i)cin>>V[i];
for(int i=1;i<=n;++i)nd[i]=s[i]!=s[n-i+1],val[i]=1e18;
for(int i=1;i<=n;++i)if(nd[i])pr=i;
if(!pr){for(int i=1;i<=n;++i)cout<<"0 ";cout<<"\n";continue;}
pl=n-pr+1;
{
long long mn=0,t;int z;
for(int i=pr;i>n/2;--i)if(nd[i])mn+=V[i],z=i;
val[pr]=1ll*(pr-z)*C+mn;
for(int i=n/2;i>pl;--i)
{
if(nd[i])mn-=V[n-i+1]-min(V[i],V[n-i+1]),
val[pr]=min(val[pr],1ll*(pr-i)*C+mn);
val[i]=1ll*(pr-i)*C+mn;
}
}
{
long long mn=0;int z;
for(int i=pl;i<=n/2;++i)if(nd[i])mn+=V[i],z=i;
val[pl]=1ll*(z-pl)*C+mn;
for(int i=n/2+1;i<pr;++i)
{
if(nd[i])mn-=V[n-i+1]-min(V[i],V[n-i+1]),
val[pr]=min(val[pr],1ll*(i-pl)*C+mn);
val[i]=1ll*(i-pl)*C+mn;
}
}
for(int i=2;i<=n;++i)val[i]=min(val[i],val[i-1]+C);
for(int i=n-1;i;--i)val[i]=min(val[i],val[i+1]+C);
for(int i=1;i<=n;++i)cout<<val[i]<<' ';cout<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9768kb
input:
2 5 1 ABCDE 7 1 4 5 1 5 1 ABCDA 7 1 4 5 1
output:
6 5 6 6 5 2 1 2 3 4
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 9752kb
input:
1 10 4 AABABBABAB 10 3 4 10 7 1 8 10 7 6
output:
10 14 18 22 26 22 18 14 10 6
result:
ok 10 numbers
Test #3:
score: -100
Wrong Answer
time: 21ms
memory: 7636kb
input:
10000 10 4 ABBBAABABB 6 10 3 9 1 8 5 4 4 10 10 4 BABBAAABAB 3 7 5 9 2 3 9 8 4 1 10 4 ABBBAAABAA 3 2 4 8 2 9 1 9 6 3 10 4 BBAABBAABB 8 8 10 7 1 1 4 9 6 4 10 4 BAABBBBBAB 5 7 3 5 4 2 1 8 2 8 10 4 ABAAAABABA 10 8 2 7 5 3 7 8 10 5 10 4 BBABABAABA 10 6 10 2 2 6 4 4 3 9 10 4 BBBAAAABBB 7 2 2 8 9 10 10 6 7...
output:
17 21 25 29 33 29 33 30 26 22 21 17 13 9 13 13 9 13 17 21 22 18 22 26 23 26 23 19 15 19 0 0 0 0 0 0 0 0 0 0 11 7 3 7 11 15 12 8 12 16 19 15 11 7 11 11 7 11 15 19 30 34 38 37 35 34 38 42 38 34 0 0 0 0 0 0 0 0 0 0 11 7 3 7 11 13 9 5 9 13 8 4 8 12 16 14 10 6 2 6 18 14 10 6 10 14 10 14 18 22 ...
result:
wrong answer 3rd numbers differ - expected: '17', found: '25'