#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i]
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)>>1)
#define mod 1000000007
#define inf 1000000009
#define N 405
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
int n, ans, a[N], say[5], dp[N][N][N][5], pre[N][5], yer[5][N];
map < char , int > h;
int f(int r, int g, int y, int lst){
if(r < 0 or g < 0 or y < 0)
return inf;
if(r + g + y == 0)
return 0;
int &ans = dp[r][g][y][lst];
if(ans != -1)
return ans;
ans = inf;
if(lst == 1){//r yapcan
int ind = yer[1][r];
int rr = min(r, pre[ind][1]);
int gg = min(g, pre[ind][2]);
int yy = min(y, pre[ind][3]);
int of = max(0, ind - rr - gg - yy);
ans = min(ans, f(r - 1, g, y, 2) + of);
ans = min(ans, f(r - 1, g, y, 3) + of);
}
if(lst == 2){//g yapcan
int ind = yer[2][g];
int rr = min(r, pre[ind][1]);
int gg = min(g, pre[ind][2]);
int yy = min(y, pre[ind][3]);
int of = max(0, ind - rr - gg - yy);
ans = min(ans, f(r, g - 1, y, 1) + of);
ans = min(ans, f(r, g - 1, y, 3) + of);
// cout << ind << " " << rr << " " << gg << " " << yy << " -> ";
}
if(lst == 3){//y yapcan
int ind = yer[3][y];
int rr = min(r, pre[ind][1]);
int gg = min(g, pre[ind][2]);
int yy = min(y, pre[ind][3]);
int of = max(0, ind - rr - gg - yy);
ans = min(ans, f(r, g, y - 1, 1) + of);
ans = min(ans, f(r, g, y - 1, 2) + of);
// cout << ind << " " << rr << " " << gg << " " << yy << " -> ";
}
// cout << r << " " << g << " " << y << " " << lst << " = " << ans << endl;
return ans;
}
int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
memset(dp, -1, sizeof dp);
h['R'] = 1;
h['G'] = 2;
h['Y'] = 3;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
char x;
scanf(" %c",&x);
a[i] = h[x];
say[a[i]]++;
yer[a[i]][say[a[i]]] = i;
for(int j = 1; j <= 3; j++)
pre[i][j] = pre[i - 1][j] + (a[i] == j);
}
ans = min(min(f(say[1], say[2], say[3], 1), f(say[1], say[2], say[3], 2)), f(say[1], say[2], say[3], 3));
if(ans >= inf)
printf("-1\n");
else
printf("%d\n", ans);
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:72: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:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
910 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
910 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
884 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
910 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
