Submission #155675

#TimeUsernameProblemLanguageResultExecution timeMemory
155675popovicirobertGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
157 ms99420 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long #if 0 const int MOD = ; inline int lgput(int a, int b) { int ans = 1; while(b > 0) { if(b & 1) ans = (1LL * ans * a) % MOD; b >>= 1; a = (1LL * a * a) % MOD; } return ans; } inline void mod(int &x) { if(x >= MOD) x -= MOD; } inline void add(int &x, int y) { x += y; mod(x); } inline void sub(int &x, int y) { x += MOD - y; mod(x); } inline void mul(int &x, int y) { x = (1LL * x * y) % MOD; } inline int inv(int x) { return lgput(x, MOD - 2); } #endif #if 0 int fact[], invfact[]; inline void prec(int n) { fact[0] = 1; for(int i = 1; i <= n; i++) { fact[i] = (1LL * fact[i - 1] * i) % MOD; } invfact[n] = lgput(fact[n], MOD - 2); for(int i = n - 1; i >= 0; i--) { invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD; } } inline int comb(int n, int k) { if(n < k) return 0; return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD; } #endif using namespace std; const int INF = 1e9; const int MAXN = 400; int dp[MAXN + 1][MAXN + 1][MAXN + 1][3]; int num[3][3][MAXN + 1][MAXN + 1]; int main() { #if 0 ifstream cin("A.in"); ofstream cout("A.out"); #endif int i, j, n; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); string str; cin >> n >> str; str = " " + str; vector <int> ind('Z'), fr(3), pos[3]; ind['R'] = 0, ind['Y'] = 1, ind['G'] = 2; for(i = 1; i <= n; i++) { str[i] = ind[str[i]]; fr[str[i]]++; } for(i = 0; i < 3; i++) { pos[i].push_back(0); } for(i = 1; i <= n; i++) { pos[str[i]].push_back(i); } for(int a = 0; a < 3; a++) { for(int b = 0; b < 3; b++) { for(i = 0; i <= fr[a]; i++) { int cnt = 0; for(j = 0; j <= fr[b]; j++) { if(pos[a][i] < pos[b][j]) { cnt++; } num[a][b][i][j] = cnt; } } } } for(int a = 0; a <= fr[0]; a++) { for(int b = 0; b <= fr[1]; b++) { for(int c = 0; c <= fr[2]; c++) { for(i = 0; i < 3; i++) { dp[a][b][c][i] = INF; } } } } for(i = 0; i < 3; i++) { dp[0][0][0][i] = 0; } for(int a = 0; a <= fr[0]; a++) { for(int b = 0; b <= fr[1]; b++) { for(int c = 0; c <= fr[2]; c++) { int p = a + b + c; if(p == 0) continue; for(int d = 0; d < 3; d++) { for(int e = 0; e < 3; e++) { if(d == e) continue; int cur; if(d == 0) { if(a == 0) continue; cur = dp[a - 1][b][c][e] + (pos[0][a] + num[0][1][a][b] + num[0][2][a][c]) - p; } if(d == 1) { if(b == 0) continue; cur = dp[a][b - 1][c][e] + (pos[1][b] + num[1][0][b][a] + num[1][2][b][c]) - p; } if(d == 2) { if(c == 0) continue; cur = dp[a][b][c - 1][e] + (pos[2][c] + num[2][0][c][a] + num[2][1][c][b]) - p; } dp[a][b][c][d] = min(dp[a][b][c][d], cur); } } } } } int ans = INF; for(i = 0; i < 3; i++) { ans = min(ans, dp[fr[0]][fr[1]][fr[2]][i]); } if(ans == INF) { ans = -1; } cout << ans; return 0; }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:97:19: warning: array subscript has type 'char' [-Wchar-subscripts]
         pos[str[i]].push_back(i);
                   ^
joi2019_ho_t3.cpp:139:29: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
                         int cur;
                             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...