Submission #110439

#TimeUsernameProblemLanguageResultExecution timeMemory
110439pamajGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
15 / 100
8 ms640 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 410; int n; long long ans = 1e18; string s; void generate(int a, int b, int c, string crct) { if((int)crct.size() == n) { vector<int> v1r, v1g, v1y; vector<int> v2r, v2g, v2y; for(int i = 0; i < n; i++) { if(s[i] == 'R') { v1r.push_back(i); } if(s[i] == 'G') { v1g.push_back(i); } if(s[i] == 'Y') { v1y.push_back(i); } if(crct[i] == 'R') { v2r.push_back(i); } if(crct[i] == 'G') { v2g.push_back(i); } if(crct[i] == 'Y') { v2y.push_back(i); } } long long num_dif = 0; for(int i = 0; i < (int)v1y.size(); i++) { num_dif += abs(v1y[i] - v2y[i]); } for(int i = 0; i < (int)v1r.size(); i++) { num_dif += abs(v1r[i] - v2r[i]); } for(int i = 0; i < (int)v1g.size(); i++) { num_dif += abs(v1g[i] - v2g[i]); } ans = min(ans, num_dif/2); return; } else { if((int)crct.size()) { if(a) { char last = crct[crct.size() - 1]; if(last != 'R') generate(a - 1, b, c, crct + "R"); } if(b) { char last = crct[crct.size() - 1]; if(last != 'G') generate(a, b - 1, c, crct + "G"); } if(c) { char last = crct[crct.size() - 1]; if(last != 'Y') generate(a, b, c - 1, crct + "Y"); } } else if((int)crct.size() == 0) { if(a) generate(a - 1, b, c, crct + "R"); if(b) generate(a, b - 1, c, crct + "G"); if(c) generate(a, b, c - 1, crct + "Y"); } } } string vazia; int qt[4]; int main() { cin >> n; for(int i = 0; i < n; i++) { char c; cin >> c; int tipo; if(c == 'R') tipo = 1; else if(c == 'G') tipo = 2; else tipo = 3; qt[tipo]++; s += c; } string crct; int metade = n/2 + (n % 2 == 1); int cont = 0; generate(qt[1], qt[2], qt[3], vazia); cout << (ans == (long long)1e18 ? -1 : ans) << "\n"; }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:118:6: warning: unused variable 'metade' [-Wunused-variable]
  int metade = n/2 + (n % 2 == 1);
      ^~~~~~
joi2019_ho_t3.cpp:120:6: warning: unused variable 'cont' [-Wunused-variable]
  int cont = 0;
      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...