Submission #948689

#	Time	Username	Problem	Language	Result	Execution time	Memory
948689		vjudge306	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	82 ms	100340 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<ll, null_type, less_equal<ll>, 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
//#define int long long
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));
int dp[204][204][204][3], n;
int nm(int i, int x, int a, int b, int c, int ar[][3], vector<int>pos[]) {
bool f=0;
if(x==0&&a==ar[n-1][0]) f=1;
if (x==1&&ar[n-1][1]==b) f=1;
if (x==2&&ar[n-1][2]==c) f=1;
if (f) return 1000000;

int j;
switch(x) {
case 0:
    j=pos[x][a]; break;
case 1:
    j=pos[x][b]; break;
default:
    j=pos[x][c]; break;
}
int rn=max(0, a-ar[j][0]), gn=max(0, b-ar[j][1]), yn=max(0, c-ar[j][2]);
return rn+gn+yn+(j-i)-1;
}
int main() {

    x_x
  string s; cin>>n>>s; memset(dp, -1, sizeof(dp));
  int ar[n][3]; vector<int>pos[3];
  for (int i=0; i<n; i++) {
    ar[i][0]=ar[i][1]=ar[i][2]=0;
    switch(s[i]) {
case 'R':
    ar[i][0]++, pos[0].emp(i);
    break;
case 'G':
    ar[i][1]++, pos[1].emp(i);
    break;
case 'Y':
    ar[i][2]++, pos[2].emp(i);
    break;
default:
    break;
    }
    for(int j=0; j<3&&i; j++) ar[i][j]+=ar[i-1][j];
  }

  int zero=0; for (int i=0; i<3; i++) zero+=(ar[n-1][i]==0);
  if (zero>1) return cout<<0, 0;

  int mx=max({ar[n-1][0], ar[n-1][1], ar[n-1][2]}), rst=n-mx; --mx;
  if (mx>rst) return cout<<-1, 0;

  for (int ind=0; ind<n; ind++) {
    for (int a=0; a<=min(ar[n-1][0],ind); a++) {
        for (int b=0; b<=min(ind,ar[n-1][1])&&(a+b<=ind); b++) {
            int c=ind-(a+b); if(c>ar[n-1][2]) continue;

            mx=max({a,b,c}), rst=ind-mx; --mx;
            if (mx>rst)
                {/*dp[a+1][b][c][0]=dp[a][b+1][c][1]=dp[a][b][c+1][2]=1000000;*/ continue;}

            int m[3];
            m[0]=nm(ind-1, 0, a, b, c, ar, pos);
            m[1]=nm(ind-1, 1, a, b, c, ar, pos), m[2]=nm(ind-1, 2, a, b, c, ar, pos);
            if (!ind) {
                dp[1][0][0][0]=m[0]; dp[0][1][0][1]=m[1]; dp[0][0][1][2]=m[2];
            }
            else {
               for (int k=0; k<3; k++) {
                    if (k==0&&!a)continue; if (k==1&&!b)continue; if (k==2&&!c)continue;
                for (int r=0; r<3; r++) {
                    if (r!=k) {
                     int x=a+(r==0), y=b+(r==1), z=c+(r==2);
                    if (x>ar[n-1][0]||y>ar[n-1][1]||z>ar[n-1][2]) continue;
                    if (dp[x][y][z][r]==-1) dp[x][y][z][r]=1000000;
                    if (dp[a][b][c][k]==-1) continue;
                    dp[x][y][z][r]=min(dp[x][y][z][r], m[r]+dp[a][b][c][k]);
                    }
                }
               }
            }
        }
    }
  }

  int a=ar[n-1][0], b=ar[n-1][1], c=ar[n-1][2];

  int ans=INT_MAX;
  for (int r=0; r<3; r++) if(dp[a][b][c][r]>-1)ans=min(ans, dp[a][b][c][r]);
  cout<<(ans>=1000000?-1:ans);
  return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:86:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   86 |                     if (k==0&&!a)continue; if (k==1&&!b)continue; if (k==2&&!c)continue;
      |                     ^~
joi2019_ho_t3.cpp:86:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   86 |                     if (k==0&&!a)continue; if (k==1&&!b)continue; if (k==2&&!c)continue;
      |                                            ^~

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