Submission #99673

#	Time	Username	Problem	Language	Result	Execution time	Memory
99673		cki86201	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	100 / 100	76 ms	65020 KiB

joi2019_ho_t3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N;
int X[410];
char buf[410];
int lc[3][410][3], cnt[3], w[3][410];
int dp[410][205][135][3];

void upd(int &a, int b) {
	if(a > b) a = b;
}

int main() {
	scanf("%d", &N);
	scanf("%s", buf + 1);
	for(int i=1;i<=N;i++) X[i] = (buf[i] == 'Y' ? 0 : buf[i] == 'G' ? 1 : 2);
	pii tcnt[3] = {};
	rep(i, 3) tcnt[i].Se = i;
	for(int i=1;i<=N;i++) tcnt[X[i]].Fi++;
	sort(tcnt, tcnt + 3);
	for(int i=1;i<=N;i++) {
		rep(u, 3) if(X[i] == tcnt[u].Se) { X[i] = 2 - u; break; }
	}
	for(int i=1;i<=N;i++) {
		int v = X[i];
		cnt[v]++;
		w[v][cnt[v]] = i;
		rep(a, 3) lc[v][cnt[v]][a] = cnt[a];
	}
	for(int i=0;i<=cnt[0];i++) for(int j=0;j<=cnt[1];j++) for(int k=0;k<=cnt[2];k++) rep(v, 3) dp[i][j][k][v] = 1e9;
	rep(u, 3) dp[0][0][0][u] = 0;
	for(int i=0;i<=cnt[0];i++) for(int j=0;j<=cnt[1];j++) for(int k=0;k<=cnt[2];k++) rep(v, 3) {
		int val = dp[i][j][k][v];
		if(val > 1e6) continue;
		if(i < cnt[0] && v != 0) {
			int r = w[0][i+1] - 1;
			r -= min(lc[0][i+1][0], i) + min(lc[0][i+1][1], j) + min(lc[0][i+1][2], k);
			upd(dp[i+1][j][k][0], r + val);
		}
		if(j < cnt[1] && v != 1) {
			int r = w[1][j+1] - 1;
			r -= min(lc[1][j+1][0], i) + min(lc[1][j+1][1], j) + min(lc[1][j+1][2], k);
			upd(dp[i][j+1][k][1], r + val);
		}
		if(k < cnt[2] && v != 2) {
			int r = w[2][k+1] - 1;
			r -= min(lc[2][k+1][0], i) + min(lc[2][k+1][1], j) + min(lc[2][k+1][2], k);
			upd(dp[i][j][k+1][2], r + val);
		}
	}
	int ans = 1e9;
	rep(u, 3) ans = min(ans, dp[cnt[0]][cnt[1]][cnt[2]][u]);
	if(ans < 1e9) printf("%d\n", ans);
	else puts("-1");
	return 0;
}

Compilation message (stderr)

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

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