oj.uz

Submission #947844

# Submission time Handle Problem Language Result Execution time Memory
947844 2024-03-17T06:22:50 Z vjudge306 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 46 ms 135264 KB 
#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=(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;
}
/*1 2 3 4 5 6
1 2 3 4 5 6
1 2 6 3 4 5
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 135128 KB Output is correct
2 Correct 17 ms 135260 KB Output is correct
3 Incorrect 18 ms 135264 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 135128 KB Output is correct
2 Correct 17 ms 135260 KB Output is correct
3 Incorrect 18 ms 135264 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 135260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 135128 KB Output is correct
2 Correct 17 ms 135260 KB Output is correct
3 Incorrect 18 ms 135264 KB Output isn't correct
4 Halted 0 ms 0 KB -