oj.uz

Submission #707051

# Submission time Handle Problem Language Result Execution time Memory
707051 2023-03-08T11:03:58 Z blacktulip Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 453 ms 1002364 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,dp[li][li][li][4],ind1[3][li],ind2[3][li],ind[3][li];
int cev;
string s;
vector<int> v[3];
 
inline int in(){
    int x;
    scanf("%d",&x);
    return x;
}

inline int f(int bir,int iki,int uc,int sira,int son){
	int cevv=1000000000;
	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)+max(0,(v[0][bir]+max(0,iki-ind[1][bir]-1)+max(0,uc-ind[2][bir]-1))-sira));
	}
	if(iki!=siz2){
		if(son!=1)cevv=min(cevv,f(bir,iki+1,uc,sira+1,1)+max(0,(v[1][iki]+max(0,bir-ind1[0][iki]-1)+max(0,uc-ind1[2][iki]-1))-sira));
	}
	if(uc!=siz3){
		if(son!=2)cevv=min(cevv,f(bir,iki,uc+1,sira+1,2)+max(0,(v[2][uc]+max(0,iki-ind2[1][uc]-1)+max(0,bir-ind2[0][uc]-1))-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);
	}
	for(int i=0;i<(int)v[0].size();i++){
		for(int j=0;j<(int)v[1].size();j++){
			if(v[1][j]>v[0][i]){break;}
			ind[1][i]=j;
		}
		for(int j=0;j<(int)v[2].size();j++){
			if(v[2][j]>v[0][i]){break;}
			ind[2][i]=j;
		}
		
	}
	for(int i=0;i<(int)v[1].size();i++){
		for(int j=0;j<(int)v[0].size();j++){
			if(v[0][j]>v[1][i]){break;}
			ind1[0][i]=j;
		}
		for(int j=0;j<(int)v[2].size();j++){
			if(v[2][j]>v[1][i]){break;}
			ind1[2][i]=j;
		}
		
	}
	for(int i=0;i<(int)v[2].size();i++){
		for(int j=0;j<(int)v[0].size();j++){
			if(v[0][j]>v[2][i]){break;}
			ind2[0][i]=j;
		}
		for(int j=0;j<(int)v[1].size();j++){
			if(v[1][j]>v[2][i]){break;}
			ind2[1][i]=j;
		}
		//~ cout<<i<<" :: "<<ind2[0][i]<<" :: "<<ind2[1][i]<<endl;
	}
	int yaz=f(0,0,0,0,3);
	if(yaz>=1000000000)yaz=-1;
	cout<<yaz;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 1002168 KB Output is correct
2 Correct 394 ms 1002232 KB Output is correct
3 Correct 385 ms 1002160 KB Output is correct
4 Correct 367 ms 1002236 KB Output is correct
5 Correct 365 ms 1002268 KB Output is correct
6 Correct 365 ms 1002180 KB Output is correct
7 Correct 364 ms 1002184 KB Output is correct
8 Correct 377 ms 1002364 KB Output is correct
9 Correct 381 ms 1002180 KB Output is correct
10 Correct 370 ms 1002176 KB Output is correct
11 Incorrect 368 ms 1002180 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 1002168 KB Output is correct
2 Correct 394 ms 1002232 KB Output is correct
3 Correct 385 ms 1002160 KB Output is correct
4 Correct 367 ms 1002236 KB Output is correct
5 Correct 365 ms 1002268 KB Output is correct
6 Correct 365 ms 1002180 KB Output is correct
7 Correct 364 ms 1002184 KB Output is correct
8 Correct 377 ms 1002364 KB Output is correct
9 Correct 381 ms 1002180 KB Output is correct
10 Correct 370 ms 1002176 KB Output is correct
11 Incorrect 368 ms 1002180 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 1002188 KB Output is correct
2 Correct 367 ms 1002188 KB Output is correct
3 Correct 375 ms 1002216 KB Output is correct
4 Correct 367 ms 1002188 KB Output is correct
5 Correct 368 ms 1002296 KB Output is correct
6 Correct 366 ms 1002188 KB Output is correct
7 Correct 374 ms 1002188 KB Output is correct
8 Correct 359 ms 1002248 KB Output is correct
9 Correct 366 ms 1002284 KB Output is correct
10 Correct 366 ms 1002244 KB Output is correct
11 Correct 363 ms 1002196 KB Output is correct
12 Correct 376 ms 1002188 KB Output is correct
13 Correct 366 ms 1002184 KB Output is correct
14 Correct 368 ms 1002252 KB Output is correct
15 Correct 368 ms 1002276 KB Output is correct
16 Correct 375 ms 1002248 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 1002168 KB Output is correct
2 Correct 394 ms 1002232 KB Output is correct
3 Correct 385 ms 1002160 KB Output is correct
4 Correct 367 ms 1002236 KB Output is correct
5 Correct 365 ms 1002268 KB Output is correct
6 Correct 365 ms 1002180 KB Output is correct
7 Correct 364 ms 1002184 KB Output is correct
8 Correct 377 ms 1002364 KB Output is correct
9 Correct 381 ms 1002180 KB Output is correct
10 Correct 370 ms 1002176 KB Output is correct
11 Incorrect 368 ms 1002180 KB Output isn't correct
12 Halted 0 ms 0 KB -