Submission #165629

#	Time	Username	Problem	Language	Result	Execution time	Memory
165629		cbertram	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	1065 ms	310008 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<vll> vvll;
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i = a; i < b; i++)
#define relax(a, b) a = min(a,b)
#define posNow(pos,behind,c,i,R,G,Y) pos[c][i]+max(0,R-behind[0][pos[c][i]])+max(0,G-behind[1][pos[c][i]])+max(0,Y-behind[2][pos[c][i]])

int posNow2(vvi &pos, vvi &behind, int c, int i, int R, int G, int Y) {
  int p = pos[c][i];
  return p+max(0,R-behind[0][p])+max(0,G-behind[1][p])+max(0,Y-behind[2][p]);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int NN;
  cin >> NN;
  const int N = NN;
  vi S(N);
  string sS;
  cin >> sS;
  rep(n,0,N) {
    switch(sS[n]) {
    case 'R': S[n] = 0; break;
    case 'G': S[n] = 1; break;
    case 'Y': S[n] = 2; break;
    }
  }
  vvi pos(3, vi(0));
  rep(n,0,N) pos[S[n]].push_back(n);
  const int PS0 = (int)pos[0].size();
  const int PS1 = (int)pos[1].size();
  const int PS2 = (int)pos[2].size();
  vvi behind(3, vi(N+1));
  rep(c,0,3) {
    int i = 0;
    rep(n,0,N+1) {
      behind[c][n] = i;
      if(i < (int)pos[c].size() && pos[c][i] == n) i++;
    }
  }
  vvvvi steps(PS0+2, vvvi(PS1+2, vvi(PS2+2, vi(3, 1000000000))));
  vvvvb vis(PS0+2, vvvb(PS1+2, vvb(PS2+2, vb(3))));
  steps[0][0][0][0] = 0;
  steps[0][0][0][1] = 0;
  steps[0][0][0][2] = 0;
  queue<int> q;
  q.push(0);
  q.push(1);
  q.push(2);
  while(!q.empty()) {
    int front = q.front();
    q.pop();
    int R = front/3/N/N;
    int G = (front/3/N)%N;
    int Y = (front/3)%N;
    int C = front%3;
    int here = steps[R][G][Y][C];
    int used = R+G+Y;
    if(here == 1000000000) continue;
    if(R < PS0 && !vis[R+1][G][Y][0]) {
      vis[R+1][G][Y][0] = true;
      q.push(front+N*N*3 -C+0);
    }
    if(G < PS1 && !vis[R][G+1][Y][1]) {
      vis[R][G+1][Y][1] = true;
      q.push(front+N*3 -C+1);
    }
    if(Y < PS2 && !vis[R][G][Y+1][2]) {
      vis[R][G][Y+1][2] = true;
      q.push(front+3 -C+2);
    }
    //cerr << "(R,G,Y,C) = ("<<R<<", "<<G<<", "<<Y<<", "<<C<<") "<<here<<"\n";
    if(R < PS0 && C != 0) relax(steps[R+1][G][Y][0], here+posNow(pos, behind, 0, R, R, G, Y)-used);
    if(G < PS1 && C != 1) relax(steps[R][G+1][Y][1], here+posNow(pos, behind, 1, G, R, G, Y)-used);
    if(Y < PS2 && C != 2) relax(steps[R][G][Y+1][2], here+posNow(pos, behind, 2, Y, R, G, Y)-used);
  }

  int res = 1000000000;
  relax(res, steps[PS0][PS1][PS2][0]);
  relax(res, steps[PS0][PS1][PS2][1]);
  relax(res, steps[PS0][PS1][PS2][2]);
  if(res == 1000000000)
    cout << "-1\n";
  else
    cout << res << '\n';
}

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