Submission #377957

#	Time	Username	Problem	Language	Result	Execution time	Memory
377957		astoria	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1 ms	364 KiB

joi2019_ho_t3

#include "bits/stdc++.h"
using namespace std;

int mn(int x, int y){
	if(x!=-1&&y!=-1) return min(x,y);
	else if(x!=-1) return x;
	else return y;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n; cin>>n;
	string s; int a[n+5];
	cin>>s;
	s='0'+s;
	int ct[2]; memset(ct,0,sizeof(ct));
	vector<int> p[2];
	for(int i=1; i<=n; i++){
		if(s[i]=='R') a[i]=0;
		else a[i]=1;
		ct[a[i]]++;
		p[a[i]].push_back(i);
	}
	
	if(abs(ct[0]-ct[1]) > 1){ cout<<-1; return 0;}
	
	int dp[n+5][2]; memset(dp,-1,sizeof(dp));
	dp[1][a[1]] = 0;
	
	if(a[1]==0){
		int fs;
		for(int i=2; i<=n; i++){
			if(a[i]==1){ fs=i; break;}
		}
		dp[1][1] = fs-1;
	}
	else{
		int fs;
		for(int i=2; i<=n; i++){
			if(a[i]==0){ fs=i; break;}
		}
		dp[1][0] = fs-1;
	}
	
	for(int i=2; i<=n; i++){
		for(int j=0; j<=1; j++){
			int num[2];
			num[j] = (n+1)/2;
			num[!j] = n/2;
			for(int k=0; k<=1; k++){
				int crp;
				if(k==a[i-1]) crp=a[i-1];
				else crp=a[i];
				if(crp==j) dp[i][j] = mn(dp[i][j],dp[i-1][k]);
				else{
					dp[i][j] = mn(dp[i][j], dp[i-1][k] + p[j][num[j]]);
				}
			}
		}
	}
	
	if(ct[0]>ct[1]) cout<<dp[n][0];
	else if(ct[1]>ct[0]) cout<<dp[n][1];
	else cout<<mn(dp[n][0],dp[n][1]);
	
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:43:16: warning: 'fs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |   dp[1][0] = fs-1;
      |              ~~^~
joi2019_ho_t3.cpp:36:16: warning: 'fs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |   dp[1][1] = fs-1;
      |              ~~^~

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