Submission #201254

#	Time	Username	Problem	Language	Result	Execution time	Memory
201254		abil	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	498 ms	88568 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
//#define int long long

using namespace std;

const int N = (1e6 + 12);
const int mod = (1e9 + 7);
const int inf = (1e9 + 7);

vector<int > vec[3];
int dp[4][250][150][150];
int n;

int go(int x,int ig, int iy,int ir){
	if(ig + iy + ir == n){
		return 0;
	}
	if(dp[x][ig][iy][ir] != -1){
		return dp[x][ig][iy][ir];
	}
	int ind = ig + ir + iy, ans = inf;
	for(int i = 0;i < 3; i++){
		if(i == x){
			continue;
		}
		if(i == 0){
			if(ig == vec[0].size()){
				continue;
			}
			int id = vec[0][ig], ad = 0;
			ad -= lower_bound(vec[1].begin(), vec[1].begin() + iy, id) - vec[1].begin();
			ad += iy;
			ad -= lower_bound(vec[2].begin(), vec[2].begin() + ir, id) - vec[2].begin();
			ad += ir;
			ans = min(ans, go(i, ig + 1, iy, ir) + abs((ad + id) - ind));
		}
		if(i == 1){
			if(iy == vec[1].size()){
				continue;
			}
			int id = vec[1][iy], ad = 0;
			ad -= lower_bound(vec[0].begin(), vec[0].begin() + ig, id) - vec[0].begin();
			ad += ig;
			ad -= lower_bound(vec[2].begin(), vec[2].begin() + ir, id) - vec[2].begin();
			ad += ir;
			ans = min(ans, go(i, ig, iy + 1, ir) + abs((ad + id) - ind));
		}
		if(i == 2){
			if(ir == vec[2].size()){
				continue;
			}
			int id = vec[2][ir], ad = 0;
			ad -= lower_bound(vec[1].begin(), vec[1].begin() + iy, id) - vec[1].begin();
			ad += iy;
			ad -= lower_bound(vec[0].begin(), vec[0].begin() + ig, id) - vec[0].begin();
			ad += ig;
			ans = min(ans, go(i, ig , iy, ir + 1) + abs((ad + id) - ind));
		}
	}
	dp[x][ig][iy][ir] = ans;
	return ans;
}

main(){
	char ch;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf(" %c", &ch);
		if(ch == 'G'){
			vec[0].pb(i);
		}
		else
		if(ch == 'R'){
			vec[1].pb(i);
		}
		else{
			vec[2].pb(i);
		}
	}
	if(vec[1].size() < vec[2].size()){
		swap(vec[1], vec[2]);
	}
	if(vec[0].size() < vec[1].size()){
		swap(vec[1], vec[0]);
	}
	if(vec[0].size() - 1 > vec[1].size() + vec[2].size()){
		cout << -1;
		return 0;
	}
	memset(dp, -1, sizeof(dp));
	cout << go(3, 0, 0, 0);
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int go(int, int, int, int)':
joi2019_ho_t3.cpp:33:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ig == vec[0].size()){
       ~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(iy == vec[1].size()){
       ~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:55:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ir == vec[2].size()){
       ~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: At global scope:
joi2019_ho_t3.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:72: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:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &ch);
   ~~~~~^~~~~~~~~~~~

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