Submission #947849

#	Time	Username	Problem	Language	Result	Execution time	Memory
947849		vjudge306	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	562 ms	135516 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define intt int _; cin >> _; while (_--)
#define emp push_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define ld long double
#define A first
#define B second
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));
int dp[205][205][205][4], ar[405]; int n; string s; int R,G,Y;
int ans(int y, int r, int g) {
int i=r+g+y;
if(i>=n) return 0;

int k=3; if(i) k=ar[i-1];

if(i&&~dp[y][r][g][k]) return dp[y][r][g][k];

int fans=2000000;
int mx=max({(k==1)+R-r, (k==2)+G-g, (k==0)+Y-y}), sm=(k!=3)+(n-i)-mx; --mx;
if (mx>sm)
    return dp[y][r][g][k]=fans;

for(int z=0; z<3; z++) {
if(z==k) continue;
int j=i;
while(j<n&&ar[j]!=z) ++j;
if (j<n) {
int nm=0;
if(z==1)r++; else if(z==2)g++; else y++;
for (int x=j; x>i; x-=1) swap(ar[x], ar[x-1]), ++nm;
fans=min(fans,nm+ans(y,r,g));
for(int x=i; x<j; x++)swap(ar[x], ar[x+1]);

if(z==1)r-=1; else if(z==2)g-=1; else y-=1;
}
}
return dp[y][r][g][k]=fans;
}
int main() {

    x_x
 cin>>n>>s; int a=0,b=0,c=0;
for(int i=0; i<n; i++) {
if(s[i]=='R')a++, ar[i]=1; else if(s[i]=='G')b++, ar[i]=2;
else ar[i]=0, c++;
}
R=a, G=b, Y=c;
a=max({a,b,c}), b=n-a; --a;
//if(a>b) return cout<<-1, 0;
memset(dp,-1,sizeof(dp)); a=ans(0,0,0);
cout<<(a>=2000000?-1:a);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25