Submission #246463

#TimeUsernameProblemLanguageResultExecution timeMemory
246463groeneprofGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
249 ms114936 KiB
#include <bits/stdc++.h> //#define int long long #define P(x) do {if(debug) cout << x << endl;} while(false) #define H(x) P(#x << ": " << x) #define FR(i, a, b) for(int i = (a); i < (b); ++i) #define F(i, n) FR(i, 0, n) #define DR(i, a, b) for(int i = (b); i --> (a);) #define D(i, n) DR(i, 0, n) #define S(s) (int)(s).size() #define ALL(x) (x).begin(), (x).end() #define MI(x, a) (x) = min(x, a) #define MA(x, a) (x) = max(x, a) #define V vector #define pb push_back #define mp make_pair using namespace std; const bool debug = 0; const int inf = 1e9; int n; vector<int> color; vector<int> pos[3]; int dp[400][400][400][3]; bool vis[400][400][400][3]; vector<vector<int> > pref; int offset(int a[3], int i){ int res = 0; F(j,3){ res+=max(0,a[j] - pref[j][i]); } return res; } int solve(int a[3], int last){ int g = a[0], y = a[1], r = a[2]; H(g); H(y); H(r); H(last); int j = g + y + r; if(vis[g][y][r][last]){ P("visited, return: "<<dp[g][y][r][last]); return dp[g][y][r][last]; } if(g+y+r==n){ P("reached end"); return 0; } vis[g][y][r][last] = 1; dp[g][y][r][last] = inf; for(int i = 0; i<3; i++) if(i!=last && a[i] < pos[i].size()){ H(i); H(offset(a,pos[i][a[i]])); int extra = pos[i][a[i]] + offset(a,pos[i][a[i]]) - j; a[i] ++; dp[g][y][r][last] = min(dp[g][y][r][last], solve(a,i)+extra); P("a"); a[i] --; P("c"); } P("d"); P(g<<" "<<y<<" "<<r<<" "<<last<<" returns "<< dp[g][y][r][last]); return dp[g][y][r][last]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n; map<char,int> mp; color.resize(n); mp['G'] = 0; mp['Y'] = 1; mp['R'] = 2; pref.resize(3, vector<int> (n+1,0)); for(int i = 0; i<n; i++){ char c; cin>>c; color[i] = mp[c]; pos[mp[c]].push_back(i); F(j,3){ pref[j][i+1] = pref[j][i]; } pref[mp[c]][i+1]++; } int a[] = {0,0,0}; int ans = min(solve(a,0),solve(a,1)); if(ans < 1e6){ cout<<ans<<endl; } else{ cout<<-1<<endl; } return 0; }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int solve(int*, int)':
joi2019_ho_t3.cpp:49:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<3; i++) if(i!=last && a[i] < pos[i].size()){
                                         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...