oj.uz

Submission #316762

# Submission time Handle Problem Language Result Execution time Memory
316762 2020-10-27T22:42:15 Z aZvezda Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 15872 KB 
#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 = 810, offset = 410;
int dp[2][MAX_N][MAX_N][3];
int n;
string in;

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 < 2; 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;
	dp[0][offset][offset][0] = 0;
	dp[0][offset][offset][1] = 0;
	dp[0][offset][offset][2] = 0;
	for(int i = 0; i < n; i ++) { 
		int curr = i & 1, nxt = curr ^ 1;
		for(int j = 0; j < MAX_N; j ++) {
			for(int k = 0; k < MAX_N; k ++) {
				for(int last = 0; last < 3; last ++) {
					dp[nxt][j][k][last] = mod;
				}
			}
		}

		for(int j = 0; j < MAX_N; j ++) {
			for(int k = 0; k < MAX_N; k ++) {
				for(int last = 0; last < 3; last ++) {
					if(dp[curr][j][k][last] == mod) {continue;}
					int cnt[3] = {j - offset, k - offset, 0};
					cnt[2] = 0 - cnt[0] - cnt[1];
					cnt[getCode(in[i])] ++;
					for(int toGet = 0; toGet < 3; toGet ++) {
						if(toGet == last) {continue;}
						cnt[toGet] --;
						chkmin(dp[nxt][cnt[0] + offset][cnt[1] + offset][toGet], dp[curr][j][k][last] + abs(cnt[0]) + abs(cnt[1]) + abs(cnt[2]));
						cnt[toGet] ++;
					}
				}
			}
		}
	}
	int ans = mod;
	for(int i = 0; i < 3; i ++) {
		chkmin(ans, dp[n & 1][offset][offset][i]);
	}
	if(ans > MAX_N) {
		cout << -1 << endl;
	} else {
		cout << ans / 2 << endl;
	}
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int getCode(char)':
joi2019_ho_t3.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15744 KB Output is correct
2 Correct 19 ms 15864 KB Output is correct
3 Correct 20 ms 15744 KB Output is correct
4 Correct 43 ms 15792 KB Output is correct
5 Correct 60 ms 15744 KB Output is correct
6 Correct 62 ms 15864 KB Output is correct
7 Correct 59 ms 15744 KB Output is correct
8 Correct 62 ms 15744 KB Output is correct
9 Correct 61 ms 15864 KB Output is correct
10 Correct 59 ms 15864 KB Output is correct
11 Incorrect 60 ms 15864 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15744 KB Output is correct
2 Correct 19 ms 15864 KB Output is correct
3 Correct 20 ms 15744 KB Output is correct
4 Correct 43 ms 15792 KB Output is correct
5 Correct 60 ms 15744 KB Output is correct
6 Correct 62 ms 15864 KB Output is correct
7 Correct 59 ms 15744 KB Output is correct
8 Correct 62 ms 15744 KB Output is correct
9 Correct 61 ms 15864 KB Output is correct
10 Correct 59 ms 15864 KB Output is correct
11 Incorrect 60 ms 15864 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15872 KB Output is correct
2 Execution timed out 1088 ms 15744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15744 KB Output is correct
2 Correct 19 ms 15864 KB Output is correct
3 Correct 20 ms 15744 KB Output is correct
4 Correct 43 ms 15792 KB Output is correct
5 Correct 60 ms 15744 KB Output is correct
6 Correct 62 ms 15864 KB Output is correct
7 Correct 59 ms 15744 KB Output is correct
8 Correct 62 ms 15744 KB Output is correct
9 Correct 61 ms 15864 KB Output is correct
10 Correct 59 ms 15864 KB Output is correct
11 Incorrect 60 ms 15864 KB Output isn't correct
12 Halted 0 ms 0 KB -