QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#394040 | #6539. Treasure Box | starback24 | RE | 1ms | 9788kb | C++14 | 2.2kb | 2024-04-19 21:31:49 | 2024-04-19 21:31:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mkp make_pair
#define pb push_back
#define fir first
#define pp pop_back
#define eps 1e-8
#define sec second
#define pii pair<int,int>
#define eb emplace_back
#define file(filename) freopen(filename".in","r",stdin);freopen(filename".out","w",stdout);
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Dor(i,a,b) for(int i=a;i>=b;i--)
//==============================================================================================
// Fast IO
template<typename T>
inline T read(){
T f=1,c=0;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(isdigit(ch)){
c=(c<<1)+(c<<3)+(ch^48);
ch=getchar();
}
T a=f*c;
return a;
}
//=============================================================================================
//code here
char ch[1001000];
ll a1[1001000],a2[1001000];
int n,c,h[1001000];
void add(int x,int y,ll w){
a1[x]=min(a1[x],w);
a2[x]=min(a2[x],w);
a1[y]=min(a1[y],w);
a2[y]=min(a2[y],w);
}
void solve(){
cin>>n>>c;
For(i,1,n){
cin>>ch[i];
}
For(i,1,n){
cin>>h[i];
}
int l=1,r=n;
while(l<r&&ch[l]==ch[r]){
l++,r--;
}
if(l==r){
For(i,1,n){
cout<<"0 ";
}
cout<<endl;
return;
}
fill(a1,a1+n+2,sizeof(a1));
fill(a2,a2+n+2,sizeof(a2));
int p=n/2;
ll sum=0;
while(ch[p]==ch[n-p+1]){
p--;
}
For(i,l,r){
if(ch[i]!=ch[n-i+1]){
if(i<=n/2){
sum+=h[i];
}
else{
sum+=min(h[i],h[n-i+1])-h[n-i+1];
}
}
if(i>=p){
add(i,l,sum+1ll*(i-l)*c);
}
}
sum=0;
p=n-p+1;
Dor(i,r,l){
if(ch[i]!=ch[n-i+1]){
if(i>n/2){
sum+=h[i];
}
else{
sum+=min(h[i],h[n-i+1])-h[n-i+1];
}
}
if(i<=p){
add(i,r,sum+1ll*(r-i)*c);
}
}
For(i,1,n){
a1[i]=min(a1[i-1]+c,a1[i]);
}
Dor(i,n,1){
a2[i]=min(a2[i+1]+c,a2[i]);
}
For(i,1,n){
cout<<min(a1[i],a2[i])<<" ";
}
cout<<endl;
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
//吾日三省吾身
//输入多而不read()乎?
//1e18而不开longlong乎?
//多测不清乎?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9788kb
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: 1ms
memory: 7796kb
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
Runtime Error
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 17 21 25 29 26 22 26 22 21 17 13 9 13 13 9 13 17 21 22 18 22 18 22 19 15 19 15 19