제출 #961657

#제출 시각아이디문제언어결과실행 시간메모리
961657noobcodurGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
208 ms558932 KiB
#include<bits/stdc++.h>
using namespace std;

using ld = long double;

#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;

void setIO(string name){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if(!name.empty()){
		freopen((name + ".in").c_str(),"r",stdin);
		freopen((name + ".out").c_str(),"w",stdout);
	}
}

int dp[401][401][401][3],pre[3][401],freq[3],pos[3][401],arr[401];

void chmin(int &x, int y){
	x = min(x,y);
}

signed main(){
	setIO("");
	int n; cin >> n;
	string a; cin >> a;

	forn(i,n){
		if(a[i] == 'R') arr[i] = 0;
		if(a[i] == 'G') arr[i] = 1;
		if(a[i] == 'Y') arr[i] = 2;
	}

	forn(i,n){
		freq[arr[i]]++;
		pos[arr[i]][freq[arr[i]]-1] = i;

		forn(j,3) pre[j][i] = freq[j];
	}

	forn(a,freq[0]+1){
		forn(b,freq[1]+1){
			forn(c,freq[2]+1){
				forn(col,3){
					dp[a][b][c][col] = INF;
				}
			}
		}
	}

	dp[0][0][0][0] = 0; dp[0][0][0][1] = 0; dp[0][0][0][2] = 0;


	forn(a,freq[0]+1){
		forn(b,freq[1]+1){
			forn(c,freq[2]+1){
				forn(col,3){
					if(col != 0 && a != freq[0]){
						int pt = pos[0][a];
						chmin(dp[a+1][b][c][0],dp[a][b][c][col]+max(0LL,pre[1][pt]-b) + max(0LL,pre[2][pt]-c));
					}

					if(col != 1 && b != freq[1]){
						int pt = pos[1][b];
						chmin(dp[a][b+1][c][1],dp[a][b][c][col]+max(0LL,pre[0][pt]-a) + max(0LL,pre[2][pt]-c));
					}

					if(col != 2 && c != freq[2]){
						int pt = pos[2][c];
						chmin(dp[a][b][c+1][2],dp[a][b][c][col]+max(0LL,pre[0][pt]-a) + max(0LL,pre[1][pt]-b));
					}
				}
			}
		}
	}

	int res = INF;

	forn(j,3){
		chmin(res,dp[freq[0]][freq[1]][freq[2]][j]);
	}

	if(res == INF){
		cout << -1 << endl; return 0;
	}

	cout << res << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t3.cpp: In function 'void setIO(std::string)':
joi2019_ho_t3.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   freopen((name + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen((name + ".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...