Submission #644147

#	Time	Username	Problem	Language	Result	Execution time	Memory
644147		ymm	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	31 ms	4308 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 410;
int dp[2][N][N][3];
vector<int> pos[3];
int dis[3][N][3];
int n;
string s;

int to_int(char c)
{
	switch (toupper(c)) {
	case 'R': return 0;
	case 'G': return 1;
	case 'Y': return 2;
	default: return -1;
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> s;
	Loop (i,0,n) pos[to_int(s[i])].push_back(i);
	Loop (i,0,3) Loop (j,0,pos[i].size()) Loop (k,0,3) {
		dis[i][j][k] = lower_bound(pos[k].begin(), pos[k].end(), pos[i][j]) - pos[k].begin();
	}
	Loop (i,0,pos[0].size()+1) {
		memset(dp[i&1], 32, sizeof(dp[i&1]));
		if (i == 0) {
			dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
		}
		Loop (j,0,pos[1].size()+1) Loop (k,0,pos[2].size()+1) {
			if (i) {
				int kooft = max(0ll, j - dis[0][i-1][1]) + max(0ll, k - dis[0][i-1][2]);
				dp[i&1][j][k][1] = min(dp[i&1][j][k][1], dp[i-1&1][j][k][0] + kooft);
				dp[i&1][j][k][2] = min(dp[i&1][j][k][2], dp[i-1&1][j][k][0] + kooft);
			}
			if (j) {
				int kooft = max(0ll, i - dis[1][j-1][0]) + max(0ll, k - dis[1][j-1][2]);
				dp[i&1][j][k][0] = min(dp[i&1][j][k][0], dp[i&1][j-1][k][1] + kooft);
				dp[i&1][j][k][2] = min(dp[i&1][j][k][2], dp[i&1][j-1][k][1] + kooft);
			}
			if (k) {
				int kooft = max(0ll, i - dis[2][k-1][0]) + max(0ll, j - dis[2][k-1][1]);
				dp[i&1][j][k][0] = min(dp[i&1][j][k][0], dp[i&1][j][k-1][2] + kooft);
				dp[i&1][j][k][1] = min(dp[i&1][j][k][1], dp[i&1][j][k-1][2] + kooft);
			}
			//printf("dp[%lld][%lld][%lld] = {%d, %d, %d}\n", i, j, k, dp[i&1][j][k][0], dp[i&1][j][k][1], dp[i&1][j][k][2]);
		}
	}
	int ans = min({dp[pos[0].size()&1][pos[1].size()][pos[2].size()][0],
	               dp[pos[0].size()&1][pos[1].size()][pos[2].size()][1],
		       dp[pos[0].size()&1][pos[1].size()][pos[2].size()][2]});
	cout << (ans > N*N? -1: ans) << '\n';
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
joi2019_ho_t3.cpp:31:15: note: in expansion of macro 'Loop'
   31 |  Loop (i,0,3) Loop (j,0,pos[i].size()) Loop (k,0,3) {
      |               ^~~~
joi2019_ho_t3.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
joi2019_ho_t3.cpp:34:2: note: in expansion of macro 'Loop'
   34 |  Loop (i,0,pos[0].size()+1) {
      |  ^~~~
joi2019_ho_t3.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
joi2019_ho_t3.cpp:39:3: note: in expansion of macro 'Loop'
   39 |   Loop (j,0,pos[1].size()+1) Loop (k,0,pos[2].size()+1) {
      |   ^~~~
joi2019_ho_t3.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
joi2019_ho_t3.cpp:39:30: note: in expansion of macro 'Loop'
   39 |   Loop (j,0,pos[1].size()+1) Loop (k,0,pos[2].size()+1) {
      |                              ^~~~
joi2019_ho_t3.cpp:42:50: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   42 |     dp[i&1][j][k][1] = min(dp[i&1][j][k][1], dp[i-1&1][j][k][0] + kooft);
      |                                                 ~^~
joi2019_ho_t3.cpp:43:50: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   43 |     dp[i&1][j][k][2] = min(dp[i&1][j][k][2], dp[i-1&1][j][k][0] + kooft);
      |                                                 ~^~

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