CF962E- Byteland, Berland and Disputed Cities （贪心）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<stack>
#include<bitset>
using namespace std;
#define mes(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(i = a; i <= b; i++)
#define dec(i,a,b) for(i = b; i >= a; i--)
#define fi first
#define se second
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,L,mid
#define rson rs,mid+1,R
typedef double db;
typedef long long int ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const ll inf = 1e15;
const int mx = 2e5+5;
const int x_move[] = {1,-1,0,0,1,1,-1,-1};
const int y_move[] = {0,0,1,-1,1,-1,1,-1};
int main(){
	int t,q,ca = 1;
	int n;
	ll pa,pb,pc;
	ll ans = 0;
	pa = pb = pc = inf;
	ll pra = 0,prb = 0;
	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		ll v;
		char str[10];
		scanf("%I64d%s",&v,str);
		if(str[0]=='R'){
			if(pa!=inf){
				pra = max(pra,v-pa);
				ans += v-pa;
			}
			pa = v;
		}
		else if(str[0]=='B'){
			if(pb!=inf){
				prb = max(prb,v-pb);
				ans += v-pb;
			}
			pb = v;
		}
		else{
			if(pb!=inf){
				prb = max(prb,v-pb);
				ans += v-pb;
			}
			if(pa!=inf){
				pra = max(pra,v-pa);
				ans += v-pa;
			}
			if(pc!=inf)
				ans = min(ans,ans+v-pc-pra-prb);
			pa = pb = pc = v;
			pra = prb = 0;
		}
	}
	printf("%I64dn",ans);
	return 0;
}