oj.uz

Submission #707022

# Submission time Handle Problem Language Result Execution time Memory
707022 2023-03-08T09:56:30 Z blacktulip Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 402 ms 1048576 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo; 
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 400;
const lo mod = 1000000007;
 
int n,m,k,flag,t,x,siz1,siz2,siz3;
int cev;
long long dp[li][li][li][4];
string s;
vector<int> v[3];
 
inline int in(){
    int x;
    scanf("%d",&x);
    return x;
}

inline long long f(int bir,int iki,int uc,int sira,int son){
	long long cevv=100000000000000000;
	if(bir==siz1 && iki==siz2 && uc==siz3)return 0;
	if(~dp[bir][iki][uc][son])return dp[bir][iki][uc][son];
	if(bir!=siz1){
		if(son!=0)cevv=min(cevv,f(bir+1,iki,uc,sira+1,0)+abs(v[0][bir]-sira));
	}
	if(iki!=siz2){
		if(son!=1)cevv=min(cevv,f(bir,iki+1,uc,sira+1,1)+abs(v[1][iki]-sira));
	}
	if(uc!=siz3){
		if(son!=2)cevv=min(cevv,f(bir,iki,uc+1,sira+1,2)+abs(v[2][uc]-sira));
	}
	return dp[bir][iki][uc][son]=cevv;
}

int main(void){
    fio();
    cin>>n;
    cin>>s;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++){
		if(s[i]=='R'){s[i]='a';siz1++;}
		if(s[i]=='G'){s[i]='b';siz2++;}
		if(s[i]=='Y'){s[i]='c';siz3++;}
		v[s[i]-'a'].pb(i);
	}
	long long yaz=f(0,0,0,0,3);
	if(yaz>=100000000000000000)yaz=-2;
	cout<<yaz/2;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 402 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 402 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 371 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 402 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -