Submission #272843

#TimeUsernameProblemLanguageResultExecution timeMemory
272843wwddGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
133 ms41472 KiB
#include <bits/stdc++.h> using namespace std; const int MN = 410; typedef long long ll; typedef vector<int> vi; typedef vector<vi> va; typedef vector<va> vb; typedef vector<vb> vc; const int INF = 1e9; struct P { int pr,pg,py; }; vc dp; vi kt[3]; vector<P> po[3]; int main() { int n; cin >> n; string s; cin >> s; for(int i=0;i<s.size();i++) { P pos{int(kt[0].size()),int(kt[1].size()),int(kt[2].size())}; if(s[i] == 'R') { kt[0].push_back(i); po[0].push_back(pos); } else if(s[i] == 'G') { kt[1].push_back(i); po[1].push_back(pos); } else { kt[2].push_back(i); po[2].push_back(pos); } } dp.assign(3,vb(kt[0].size()+1,va(kt[1].size()+1,vi(kt[2].size()+1,INF)))); dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0; for(int i=0;i<=kt[0].size();i++) { for(int j=0;j<=kt[1].size();j++) { for(int k=0;k<=kt[2].size();k++) { for(int c=0;c<3;c++) { int cur = dp[c][i][j][k]; if(c != 0 && i < kt[0].size()) { P pos = po[0][i]; int co = max(0,pos.pg-j) + max(0,pos.py-k); int& nx = dp[0][i+1][j][k]; nx = min(nx,cur+co); } if(c != 1 && j < kt[1].size()) { P pos = po[1][j]; int co = max(0,pos.pr-i) + max(0,pos.py-k); int& nx = dp[1][i][j+1][k]; nx = min(nx,cur+co); } if(c != 2 && k < kt[2].size()) { P pos = po[2][k]; int co = max(0,pos.pr-i) + max(0,pos.pg-j); int& nx = dp[2][i][j][k+1]; nx = min(nx,cur+co); } } } } } int res = INF; for(int i=0;i<3;i++) { res = min(res,dp[i][kt[0].size()][kt[1].size()][kt[2].size()]); } if(res == INF) { cout << -1 << '\n'; } else { cout << res << '\n'; } }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<s.size();i++) {
      |              ~^~~~~~~~~
joi2019_ho_t3.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<=kt[0].size();i++) {
      |              ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int j=0;j<=kt[1].size();j++) {
      |               ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    for(int k=0;k<=kt[2].size();k++) {
      |                ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |      if(c != 0 && i < kt[0].size()) {
      |                   ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |      if(c != 1 && j < kt[1].size()) {
      |                   ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |      if(c != 2 &&  k < kt[2].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...