oj.uz

답안 #217293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217293 2020-03-29T11:22:41 Z kshitij_sodani Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 499 ms 755864 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
llo mod=1000000007;
int n;
int it[401];
int dp[401][401][401][3];
vector<int> aa;
vector<int> bb;
vector<int> cc;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	char ss;
	int co=0;
	int co2=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++){
				for(int l=0;l<3;l++){
					dp[i][j][k][l]=200000;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		cin>>ss;
		if(ss=='R'){
			co+=1;
			aa.pb(i);
		}
		else if(ss=='G'){
			it[i]=1;
			co2+=1;
			bb.pb(i);
		}
		else{
			cc.pb(i);
		}
	}
	if(aa.size()>bb.size()){
		swap(aa,bb);
	}
 
	if(bb.size()>cc.size()){
		swap(cc,bb);
	}
	if(aa.size()>bb.size()){
		swap(aa,bb);
	}
	
	if(co>(n+1)/2 or co2>(n+1)/2 or (n-co-co2)>(n+1)/2){
		cout<<-1<<endl;
		return 0;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++){
				if((i+1)-j-k>(i+2)/2 or j>(i+2)/2 or k>(i+2)/2 or j+k>i+1){
					continue;
				}
			//	cout<<i+1<<" "<<j<<" "<<k<<endl;
				if(j>0 and j<=aa.size()){
					if(i>0){
						dp[i][j][k][0]=abs(i-aa[j-1])+min(dp[i-1][j-1][k][1],dp[i-1][j-1][k][2]);
					}
					else{
						dp[i][j][k][0]=abs(i-aa[j-1]);
					}
 
				}
				if(k>0 and k<=bb.size()){
					if(i>0){
						dp[i][j][k][1]=abs(i-bb[k-1])+min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][2]);
					}
					else{
						dp[i][j][k][1]=abs(i-bb[k-1]);
					}
 
				}
				if(j+k<i+1 and i+1-j-k<=cc.size()){
					if(i>0){
						dp[i][j][k][2]=min(dp[i-1][j][k][0],dp[i-1][j][k][1]);
					}
					else{
						dp[i][j][k][2]=0;
					}
				}
			//	cout<<dp[i][j][k][0]<<","<<dp[i][j][k][1]<<","<<dp[i][j][k][2]<<endl;
			}
		}
	}
	int mi=200000;
	for(int j=0;j<=3;j++){
			mi=min(mi,dp[n-1][aa.size()][bb.size()][j]);
	
	}
	cout<<mi<<endl;
 
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(j>0 and j<=aa.size()){
                ~^~~~~~~~~~~
joi2019_ho_t3.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(k>0 and k<=bb.size()){
                ~^~~~~~~~~~~
joi2019_ho_t3.cpp:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(j+k<i+1 and i+1-j-k<=cc.size()){
                    ~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 55.0

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

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 432 KB Output is correct
2 Correct 499 ms 755864 KB Output is correct
3 Correct 485 ms 753400 KB Output is correct
4 Correct 497 ms 755540 KB Output is correct
5 Correct 481 ms 755704 KB Output is correct
6 Correct 488 ms 755576 KB Output is correct
7 Correct 485 ms 753400 KB Output is correct
8 Correct 482 ms 753400 KB Output is correct
9 Correct 477 ms 749560 KB Output is correct
10 Correct 494 ms 755704 KB Output is correct
11 Correct 482 ms 755580 KB Output is correct
12 Correct 117 ms 201852 KB Output is correct
13 Correct 214 ms 356156 KB Output is correct
14 Correct 312 ms 515832 KB Output is correct
15 Correct 401 ms 755704 KB Output is correct
16 Correct 405 ms 755576 KB Output is correct

Subtask #4
0 / 25.0

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