CodeForces 632B- Alice, Bob, Two Teams
2971 단어 CodeForces
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Alice and Bob are playing a game. The game involves splitting up game pieces into two teams. There are n pieces, and the i-th piece has a strength pi.
The way to split up game pieces is split into several steps:
The strength of a player is then the sum of strengths of the pieces in the group.
Given Alice's initial split into two teams, help Bob determine an optimal strategy. Return the maximum strength he can achieve.
Input
The first line contains integer n (1 ≤ n ≤ 5·105) — the number of game pieces.
The second line contains n integers pi (1 ≤ pi ≤ 109) — the strength of the i-th piece.
The third line contains n characters A or B — the assignment of teams after the first step (after Alice's step).
Output
Print the only integer a — the maximum strength Bob can achieve.
Examples
Input
5
1 2 3 4 5
ABABA
Output
11
Input
5
1 2 3 4 5
AAAAA
Output
15
Input
1
1
B
Output
1
Note
In the first sample Bob should flip the suffix of length one.
In the second sample Bob should flip the prefix or the suffix (here it is the same) of length 5.
In the third sample Bob should do nothing.
문제 해결 방법:
수조를 앞뒤로 두루 훑어보면 폭력이면 된다.
#include
#include
#include
#define LL __int64
using namespace std;
int wc[600000];
char map[600000];
LL av(LL a,LL b,LL c)
{
LL uu=max(a,b);
uu=max(uu,c);
return uu;
}
int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
int i,j;
for(i=0;i=0;i--)
{
if(i==N-1)
{
if(map[i]=='A')
{
oo+=wc[i];
ans=wc[i]+yb;
}
if(map[i]=='B')
{
xx+=wc[i];
ans=wc[i];
}
}
else
{
if(map[i]=='A')//
{
ji=yb-xx+oo+wc[i];
oo+=wc[i];
}
if(map[i]=='B')
{
ji=yb+oo-xx;
xx+=wc[i];
}
ans=max(ans,ji);
}
}
LL av3344=av(ans,ansz,yb);
printf("%I64d
",av3344);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
문제 풀이 보고서 의 CodeForces 91B QueueOtherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest fro...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.