This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ld = long double;
#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;
void setIO(string name){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(!name.empty()){
freopen((name + ".in").c_str(),"r",stdin);
freopen((name + ".out").c_str(),"w",stdout);
}
}
int dp[401][401][401][3],pre[3][401],freq[3],pos[3][401],arr[401];
void chmin(int &x, int y){
x = min(x,y);
}
signed main(){
setIO("");
int n; cin >> n;
string a; cin >> a;
forn(i,n){
if(a[i] == 'R') arr[i] = 0;
if(a[i] == 'G') arr[i] = 1;
if(a[i] == 'Y') arr[i] = 2;
}
forn(i,n){
freq[arr[i]]++;
pos[arr[i]][freq[arr[i]]-1] = i;
forn(j,3) pre[j][i] = freq[j];
}
forn(a,freq[0]+1){
forn(b,freq[1]+1){
forn(c,freq[2]+1){
forn(col,3){
dp[a][b][c][col] = INF;
}
}
}
}
dp[0][0][0][0] = 0; dp[0][0][0][1] = 0; dp[0][0][0][2] = 0;
forn(a,freq[0]+1){
forn(b,freq[1]+1){
forn(c,freq[2]+1){
forn(col,3){
if(col != 0 && a != freq[0]){
int pt = pos[0][a];
chmin(dp[a+1][b][c][0],dp[a][b][c][col]+max(0LL,pre[1][pt]-b) + max(0LL,pre[2][pt]-c));
}
if(col != 1 && b != freq[1]){
int pt = pos[1][b];
chmin(dp[a][b+1][c][1],dp[a][b][c][col]+max(0LL,pre[0][pt]-a) + max(0LL,pre[2][pt]-c));
}
if(col != 2 && c != freq[2]){
int pt = pos[2][c];
chmin(dp[a][b][c+1][2],dp[a][b][c][col]+max(0LL,pre[0][pt]-a) + max(0LL,pre[1][pt]-b));
}
}
}
}
}
int res = INF;
forn(j,3){
chmin(res,dp[freq[0]][freq[1]][freq[2]][j]);
}
if(res == INF){
cout << -1 << endl; return 0;
}
cout << res << endl;
}
Compilation message (stderr)
joi2019_ho_t3.cpp: In function 'void setIO(std::string)':
joi2019_ho_t3.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | freopen((name + ".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen((name + ".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |