Submission #369355

#	Time	Username	Problem	Language	Result	Execution time	Memory
369355		AriaH	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	100 / 100	494 ms	502252 KiB

joi2019_ho_t3

/** Im the best because i work as hard as i possibly can **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 4e2 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 5e8;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

/// dp[tp][i][j][k] -> age 

char C[N];

string s;

int n, cnt[3], nxt[3][N][N][N], dp[3][N][N][N];

vector < int > pos[3];

inline int Less(int type, int x, int used)
{
	return lower_bound(pos[type].begin() + used, pos[type].end(), x) - pos[type].begin() - used;
}

int main()
{
	scanf("%d", &n);
	scanf("%s", C);
	s = C; s = "#" + s;
	for(int i = 1; i <= n; i ++)
	{
		if(s[i] == 'R') s[i] = '0';
		else if(s[i] == 'G') s[i] = '1';
		else s[i] = '2';
		cnt[s[i] - '0'] ++;
		pos[s[i] - '0'].push_back(i);
	}
	for(int i = 0; i <= cnt[0]; i ++)
	{
		for(int j = 0; j <= cnt[1]; j ++)
		{
			for(int k = 0; k <= cnt[2]; k ++)
			{
				if(i != cnt[0])
				{
					int id = pos[0][i];
					nxt[0][i][j][k] = Less(1, id, j) + Less(2, id, k);
				}
				else nxt[0][i][j][k] = inf;
				if(j != cnt[1])
				{
					int id = pos[1][j];
					nxt[1][i][j][k] = Less(0, id, i) + Less(2, id, k);
				}
				else nxt[1][i][j][k] = inf;
				if(k != cnt[2])
				{
					int id = pos[2][k];
					nxt[2][i][j][k] = Less(0, id, i) + Less(1, id, j);
				}	
				else nxt[2][i][j][k] = inf;
				///printf("i = %d j = %d k = %d nxt[0] = %d  nxt[1] = %d  nxt[2] = %d\n", i, j, k, nxt[0][i][j][k], nxt[1][i][j][k], nxt[2][i][j][k]);
			}
		}
	}
	///printf("\n\n");
	for(int i = 0; i < N; i ++) for(int j = 0; j < N; j ++) dp[0][0][i][j] = dp[1][0][i][j] = dp[2][0][i][j] = inf;
	dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 0; j <= min(i, cnt[0]); j ++)
		{
			for(int k = 0; k <= min(i - j, cnt[1]); k ++)
			{
				dp[0][i][j][k] = dp[1][i][j][k] = dp[2][i][j][k] = inf;
				if(i - j - k > cnt[2])
				{
					continue;
				}
				if(j) dp[0][i][j][k] = min(dp[1][i - 1][j - 1][k], dp[2][i - 1][j - 1][k]) + nxt[0][j - 1][k][i - j - k];
				if(k) dp[1][i][j][k] = min(dp[0][i - 1][j][k - 1], dp[2][i - 1][j][k - 1]) + nxt[1][j][k - 1][i - j - k];
				if(i != j + k) dp[2][i][j][k] = min(dp[0][i - 1][j][k], dp[1][i - 1][j][k]) + nxt[2][j][k][i - j - k - 1];
			}
		}
	}
	/*for(int i = 1; i <= n; i ++)
	{
		for(int j = 0; j <= cnt[0]; j ++)
		{
			for(int k = 0; k <= cnt[1]; k ++)
			{
				printf("i = %d j = %d k = %d dp[0] = %d  dp[1] = %d  dp[2] = %d\n", i, j, k, dp[0][i][j][k], dp[1][i][j][k], dp[2][i][j][k]);
			}
		}
	}
	*/
	int ans = min({dp[0][n][cnt[0]][cnt[1]], dp[1][n][cnt[0]][cnt[1]], dp[2][n][cnt[0]][cnt[1]]});
	if(ans >= inf) ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  scanf("%s", C);
      |  ~~~~~^~~~~~~~~

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