oj.uz

답안 #265185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
265185 2020-08-14T13:48:20 Z Goolakh Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1048580 KB 
// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=4e2+10, maxm=1e6+10, lg=17, mod=1e9+7, inf=1e18;

ll n,tt[3],tp[maxn][3],we[maxn][3], dp[maxn][maxn][maxn][3];
string s;
ll mem(ll c[3],ll b){
	ll &x=dp[c[0]][c[1]][c[2]][b];
	if(c[0]+c[1]+c[2]==0) return 0;
	if(x!=-1) return x;
	x=inf;
	ll tah=0; for(int g:{0,1,2}) tah=max(tah,we[c[g]][g]);
	for(int g:{0,1,2})if(c[g] && b!=g){
		c[g]--;
		ll xx=mem(c,g);
		c[g]++;
		for(int gg:{0,1,2})if(gg!=g) xx+=tp[tah][gg]-tp[we[c[g]][g]][gg];
		x=min(x,xx);
	}
	return x;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
		
	memset(dp,-1,sizeof(dp));
	cin>>n>>s;
	for(int i=0;i<n;i++){
		for(int j:{0,1,2}) tp[i][j]=tp[i-1][j];
		if(s[i]=='R') tp[i][0]++, we[++tt[0]][0]=i;
		if(s[i]=='G') tp[i][1]++, we[++tt[1]][1]=i;
		if(s[i]=='Y') tp[i][2]++, we[++tt[2]][2]=i;
	}
	ll ans=min({mem(tt,0),mem(tt,1),mem(tt,2)});
	cout<<(ans>=inf ? -1:ans);
	
	return 0;
}
// a denial a denial a denial a denial a denial a denial

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 548 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 548 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 551 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 548 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -