oj.uz

Submission #707021

# Submission time Handle Problem Language Result Execution time Memory
707021 2023-03-08T09:55:31 Z blacktulip Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 405 ms 1002332 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];
int cev;
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 Correct 387 ms 1002192 KB Output is correct
2 Correct 405 ms 1002140 KB Output is correct
3 Correct 378 ms 1002172 KB Output is correct
4 Correct 354 ms 1002272 KB Output is correct
5 Correct 353 ms 1002188 KB Output is correct
6 Correct 353 ms 1002316 KB Output is correct
7 Correct 352 ms 1002252 KB Output is correct
8 Correct 356 ms 1002300 KB Output is correct
9 Correct 355 ms 1002188 KB Output is correct
10 Incorrect 358 ms 1002188 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 1002192 KB Output is correct
2 Correct 405 ms 1002140 KB Output is correct
3 Correct 378 ms 1002172 KB Output is correct
4 Correct 354 ms 1002272 KB Output is correct
5 Correct 353 ms 1002188 KB Output is correct
6 Correct 353 ms 1002316 KB Output is correct
7 Correct 352 ms 1002252 KB Output is correct
8 Correct 356 ms 1002300 KB Output is correct
9 Correct 355 ms 1002188 KB Output is correct
10 Incorrect 358 ms 1002188 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 1002216 KB Output is correct
2 Correct 350 ms 1002168 KB Output is correct
3 Correct 359 ms 1002276 KB Output is correct
4 Correct 353 ms 1002284 KB Output is correct
5 Correct 351 ms 1002292 KB Output is correct
6 Correct 352 ms 1002316 KB Output is correct
7 Correct 362 ms 1002180 KB Output is correct
8 Correct 352 ms 1002332 KB Output is correct
9 Correct 354 ms 1002264 KB Output is correct
10 Correct 366 ms 1002184 KB Output is correct
11 Correct 376 ms 1002284 KB Output is correct
12 Correct 361 ms 1002164 KB Output is correct
13 Correct 357 ms 1002248 KB Output is correct
14 Correct 352 ms 1002188 KB Output is correct
15 Incorrect 349 ms 1002316 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 1002192 KB Output is correct
2 Correct 405 ms 1002140 KB Output is correct
3 Correct 378 ms 1002172 KB Output is correct
4 Correct 354 ms 1002272 KB Output is correct
5 Correct 353 ms 1002188 KB Output is correct
6 Correct 353 ms 1002316 KB Output is correct
7 Correct 352 ms 1002252 KB Output is correct
8 Correct 356 ms 1002300 KB Output is correct
9 Correct 355 ms 1002188 KB Output is correct
10 Incorrect 358 ms 1002188 KB Output isn't correct
11 Halted 0 ms 0 KB -