#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 2000000000
#define N 3005
#define MOD 998244353
using namespace std;
int n;
int a[405];
int dp[405][205][205][4];
int shift[5][5][405][405];
int pos[5][405];
int tot[5];
char s[405];
int f(int cur,int cnt1,int cnt2,int last) {
if(cur==n+1) return 0;
int& r=dp[cur][cnt1][cnt2][last];
if(~r) return r;
r=inf;
int cnt3=(cur-1-cnt1-cnt2);
if(last!=1) {
if(cnt1!=tot[1]) {
int add=shift[1][2][cnt1+1][cnt2]+shift[1][3][cnt1+1][cnt3];
umin(r,f(cur+1,cnt1+1,cnt2,1)+add);
}
}
if(last!=2) {
if(cnt2!=tot[2]) {
int add=shift[2][1][cnt2+1][cnt1]+shift[2][3][cnt2+1][cnt3];
umin(r,f(cur+1,cnt1,cnt2+1,2)+add);
}
}
if(last!=3) {
if(cnt3!=tot[3]) {
int add=shift[3][1][cnt3+1][cnt1]+shift[3][2][cnt3+1][cnt2];
umin(r,f(cur+1,cnt1,cnt2,3)+add);
}
}
return r;
}
void pre() {
for(int i=1;i<=n;i++) {
a[i]=(s[i]=='R'?1:s[i]=='G'?2:3);
++tot[a[i]];
pos[a[i]][tot[a[i]]]=i;
}
for(int l1=1;l1<=3;l1++) {
for(int l2=1;l2<=3;l2++) {
if(l1==l2) continue ;
for(int c1=0;c1<=tot[l1];c1++) {
int cnt=0;
for(int c2=0;c2<=tot[l2];c2++) {
cnt+=(pos[l1][c1]<pos[l2][c2]);
shift[l1][l2][c1][c2]=cnt;
cerr<<l1<<" "<<l2<<' '<<c1<<' '<<c2<<" "<< cnt<<'\n';
}
}
}
}
}
void valid() {
int cnt[99]={0};
for(int i=1;i<=n;i++) {
cnt[s[i]]++;
}
if(*max_element(cnt,cnt+99)>(n+1)/2) {
printf("-1");
exit(0);
}
}
int main() {
scanf("%d",&n);
scanf("%s",s+1);
valid();
pre();
memset(dp,-1,sizeof(dp));
printf("%d",f(1,0,0,0));
}
Compilation message
joi2019_ho_t3.cpp: In function 'void valid()':
joi2019_ho_t3.cpp:124:11: warning: array subscript has type 'char' [-Wchar-subscripts]
cnt[s[i]]++;
^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s+1);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
266908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
266908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
221 ms |
266776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
266908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
