#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,fma,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int maxn = 405;
void minq(int &a, int b) {
if(a > b) a = b;
}
int dp[maxn][maxn][maxn][3];
int n;
string s;
vi p[3];
int id(char c) {
if(c=='R') return 0;
if(c=='G') return 1;
return 2;
}
inline int cost(int i, int j, int k, int l, int w) {
if(l == w) return 1<<20;
int c, n1, n2;
if(w==0) {
c = 0;
n1 = 1;
n2 = 2;
}
if(w==1) {// i, j, k => j i k
swap(i, j);
c = 1;
n1 = 0;
n2 = 2;
}
if(w==2) {// i, j, k => k, j, i
swap(i, k);
c = 2;
n1 = 1;
n2 = 0;
}
if(p[c].size()<=i) return 1<<20;
int ans = p[c][i] - i;
int t, z;
for(t = 0, z = 1<<9; z>>=1;)
if(t+z<p[n1].size()&&p[n1][t+z]<p[c][i]) t+=z;
if(p[n1].size()&&p[n1][0]<p[c][i])
ans -= min(t+1, j);
for(t = 0, z = 1<<9; z>>=1;)
if(t+z<p[n2].size()&&p[n2][t+z]<p[c][i]) t+=z;
if(p[n2].size()&&p[n2][0]<p[c][i])
ans -= min(t+1, k);
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++) p[id(s[i])].pb(i);
memset(dp, 0x3f, sizeof dp);
dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
int ans = 1<<30;
#pragma GCC ignvd
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
for(int k = 0; k <= n; k++) {
for(int l = 0; l < 3; l++) {
if(i+j+k==n) ans = min(ans, dp[i][j][k][l]);
if(dp[i][j][k][l]>n*n) continue;
minq(dp[i+1][j][k][0], dp[i][j][k][l] + cost(i, j, k, l, 0));
minq(dp[i][j+1][k][1], dp[i][j][k][l] + cost(i, j, k, l, 1));
minq(dp[i][j][k+1][2], dp[i][j][k][l] + cost(i, j, k, l, 2));
}
}
}
}
if(ans>n*n) ans = -1;
cout << ans;
}
Compilation message
joi2019_ho_t3.cpp:65:0: warning: ignoring #pragma GCC ignvd [-Wunknown-pragmas]
#pragma GCC ignvd
joi2019_ho_t3.cpp: In function 'int cost(int, int, int, int, int)':
joi2019_ho_t3.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p[c].size()<=i) return 1<<20;
~~~~~~~~~~~^~~
joi2019_ho_t3.cpp:48:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(t+z<p[n1].size()&&p[n1][t+z]<p[c][i]) t+=z;
~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:52:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(t+z<p[n2].size()&&p[n2][t+z]<p[c][i]) t+=z;
~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
615 ms |
780360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
615 ms |
780360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
411 ms |
780280 KB |
Output is correct |
| 2 |
Execution timed out |
690 ms |
780388 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
615 ms |
780360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
