oj.uz

답안 #377958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
377958 2021-03-15T16:00:29 Z astoria Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 1 ms 364 KB 
#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]]-i);
				}
			}
		}
	}
	
	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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -