QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#394040#6539. Treasure Boxstarback24RE 1ms9788kbC++142.2kb2024-04-19 21:31:492024-04-19 21:31:51

Judging History

你现在查看的是最新测评结果

  • [2024-04-19 21:31:51]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:9788kb
  • [2024-04-19 21:31:49]
  • 提交

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 

result: