Submission #799658

#	Time	Username	Problem	Language	Result	Execution time	Memory
799658		pudelos	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	157 ms	134604 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define loop(_i, _a, _b) for(int _i=_a; _i<=_b; ++_i)
const int maxn=401, maxn2=201, inf=1e9;
int n;
int cnt[4][maxn][4];
int val[maxn];
string s;
int main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> s;
  int a=0, b=0, c=0;

  loop(i, 1, n) {
    int v;
    if(s[i-1] == 'R') v=1;
    if(s[i-1] == 'G') v=2;
    if(s[i-1] == 'Y') v=3;
    val[i]=v;
    if(v==1) {
      ++a;
      cnt[1][a][2]=b;
      cnt[1][a][3]=c;
    }
    if(v==2) {
      ++b;
      cnt[2][b][1]=a;
      cnt[2][b][3]=c;
    }
    if(v==3) {
      ++c;
      cnt[3][c][1]=a;
      cnt[3][c][2]=b;
    }
  }

  vector<vector<vector<vector<int>>>> dp(a+1, vector<vector<vector<int>>>(b+1, vector<vector<int>>(c+1, vector<int>(4, inf))));

  dp[0][0][0][1]=0;
  dp[0][0][0][2]=0;
  dp[0][0][0][3]=0;

  loop(i, 0, a) {
    loop(j, 0, b) {
      loop(k, 0, c) {
        if(i<a) dp[i+1][j][k][1]=min(dp[i+1][j][k][1], min(dp[i][j][k][2], dp[i][j][k][3])+abs(j-cnt[1][i+1][2])+abs(k-cnt[1][i+1][3]));
        if(j<b) dp[i][j+1][k][2]=min(dp[i][j+1][k][2], min(dp[i][j][k][1], dp[i][j][k][3])+abs(i-cnt[2][j+1][1])+abs(k-cnt[2][j+1][3]));
        if(k<c) dp[i][j][k+1][3]=min(dp[i][j][k+1][3], min(dp[i][j][k][1], dp[i][j][k][2])+abs(i-cnt[3][k+1][1])+abs(j-cnt[3][k+1][2]));
      }
    }
  }

  int res = inf;
  loop(i, 1, 3) res=min(res, dp[a][b][c][i]);
  if(res==inf) cout << "-1";
  else cout << res/2;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:25:5: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |     if(v==2) {
      |     ^~

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