Submission #272843

#	Time	Username	Problem	Language	Result	Execution time	Memory
272843		wwdd	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	133 ms	41472 KiB

joi2019_ho_t3

#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()) {
      |                    ~~^~~~~~~~~~~~~~

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