Submission #399881

#	Time	Username	Problem	Language	Result	Execution time	Memory
399881		SavicS	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	97 ms	163040 KiB

joi2019_ho_t3

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 405;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n;
int niz[maxn];
string s;

int dp[maxn][maxn][maxn][3]; // 0 - najmanji broj operacija, 1 - zadnja boja

int cnt[maxn][3];
vector<int> poz[maxn];

int f(char C){
   if(C == 'R')return 0;
   if(C == 'G')return 1;
   if(C == 'Y')return 2;
   assert(false);
}

int main()
{
   ios::sync_with_stdio(false);
   cout.tie(nullptr);
   cin.tie(nullptr);
   cin >> n >> s;
   ff(i,0,n - 1)niz[i + 1] = f(s[i]);

   ff(i,1,n){

      ff(j,0,2)cnt[i][j] = cnt[i - 1][j];
      cnt[i][niz[i]] += 1;

      poz[niz[i]].pb(i);

   }

   if(max({cnt[n][0], cnt[n][1], cnt[n][2]}) > (n + 1) / 2)return cout << -1, 0;
   int R = cnt[n][0], G = cnt[n][1], Y = cnt[n][2];

   ff(a,0,R)ff(b,0,G)ff(c,0,Y)ff(i,0,2)dp[a][b][c][i] = inf;

   dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
   ff(a,0,R){
      ff(b,0,G){
         ff(c,0,Y){
            ff(i,0,2){

               if(a > 0 && i != 0){
                  // stavaljam R

                  int kol = dp[a - 1][b][c][i];
                  kol += max(0, cnt[poz[0][a - 1]][1] - b);
                  kol += max(0, cnt[poz[0][a - 1]][2] - c);
                  dp[a][b][c][0] = min(dp[a][b][c][0], kol);
               }

               if(b > 0 && i != 1){
                  int kol = dp[a][b - 1][c][i];
                  kol += max(0, cnt[poz[1][b - 1]][0] - a);
                  kol += max(0, cnt[poz[1][b - 1]][2] - c);
                  dp[a][b][c][1] = min(dp[a][b][c][1], kol);
               }

               if(c > 0 && i != 2){
                  int kol = dp[a][b][c - 1][i];
                  kol += max(0, cnt[poz[2][c - 1]][0] - a);
                  kol += max(0, cnt[poz[2][c - 1]][1] - b);
                  dp[a][b][c][2] = min(dp[a][b][c][2], kol);
               }

            }
         }
      }
   }

   int rez = inf;
   ff(i,0,2)rez = min(rez, dp[R][G][Y][i]);
   cout << rez << endl;

   return 0;
}
/**

6
RRGGYY

2
RG

20
YYGYYYGGGGRGYYGRGRYG

5
RRGYY

// probati bojenje sahovski ili slicno

**/

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