Submission #316766

#	Time	Username	Problem	Language	Result	Execution time	Memory
316766		aZvezda	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	60 / 100	498 ms	809848 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 410;
int dp[MAX_N][MAX_N][MAX_N][3];
int n;
string in;
int cnt[MAX_N][3];
vector<int> ind[3];

int getCode(char c) {
	if(c == 'R') {
		return 0;
	} else if(c == 'G') {
		return 1;
	} else if(c == 'Y') {
		return 2;
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for(int i = 0; i < MAX_N; i ++) {
		for(int j = 0; j < MAX_N; j ++) {
			for(int k = 0; k < MAX_N; k ++) {
				for(int q = 0; q < 3; q ++) {
					dp[i][j][k][q] = mod;
				}
			}
		}
	} 
	cin >> n;
	cin >> in;

	for(int i = 0; i < n; i ++) {
		if(i != 0) {
			for(int j = 0; j < 3; j ++) {
				cnt[i][j] = cnt[i - 1][j];
			}
		}
		cnt[i][getCode(in[i])] ++;
		ind[getCode(in[i])].push_back(i);
	}
	
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	for(int i = 0; i <= ind[0].size(); i ++) {
		for(int j = 0; j <= ind[1].size(); j ++) {
			for(int k = 0; k <= ind[2].size(); k ++) {
				for(int last = 0; last < 3; last ++) {
					if(dp[i][j][k][last] == mod) {continue;}
					if(last != 0 && i != ind[0].size()) {
						int toGet = ind[0][i];
						int cost = max(0, cnt[toGet][1] - j) + max(0, cnt[toGet][2] - k);
						chkmin(dp[i + 1][j][k][0], dp[i][j][k][last] + cost);
					} 
					if(last != 1 && j != ind[1].size()) {
						int toGet = ind[1][j];
						int cost = max(0, cnt[toGet][0] - i) + max(0, cnt[toGet][2] - k);
						chkmin(dp[i][j + 1][k][1], dp[i][j][k][last] + cost);
					} 	
					if(last != 2 && k != ind[2].size()) {
						int toGet = ind[2][k];
						int cost = max(0, cnt[toGet][0] - i) + max(0, cnt[toGet][1] - j);
						chkmin(dp[i][j][k + 1][2], dp[i][j][k][last] + cost);
					} 
				}
			}
		}
	}
	
	int ans = mod;
	for(int i = 0; i < 3; i ++) {
		chkmin(ans, dp[ind[0].size()][ind[1].size()][ind[2].size()][i]);
	}
	
	if(ans > MAX_N) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0; i <= ind[0].size(); i ++) {
      |                 ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j = 0; j <= ind[1].size(); j ++) {
      |                  ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int k = 0; k <= ind[2].size(); k ++) {
      |                   ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |      if(last != 0 && i != ind[0].size()) {
      |                      ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |      if(last != 1 && j != ind[1].size()) {
      |                      ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |      if(last != 2 && k != ind[2].size()) {
      |                      ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int getCode(char)':
joi2019_ho_t3.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^

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