oj.uz

Submission #707033

# Submission time Handle Problem Language Result Execution time Memory
707033 2023-03-08T10:07:39 Z blacktulip Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 418 ms 1002352 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 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)+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>=1000000000)yaz=-2;
	cout<<yaz/2;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 1002224 KB Output is correct
2 Correct 358 ms 1002196 KB Output is correct
3 Correct 357 ms 1002208 KB Output is correct
4 Correct 358 ms 1002304 KB Output is correct
5 Correct 352 ms 1002336 KB Output is correct
6 Correct 360 ms 1002328 KB Output is correct
7 Correct 377 ms 1002232 KB Output is correct
8 Correct 366 ms 1002296 KB Output is correct
9 Correct 369 ms 1002240 KB Output is correct
10 Correct 362 ms 1002156 KB Output is correct
11 Incorrect 356 ms 1002188 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 1002224 KB Output is correct
2 Correct 358 ms 1002196 KB Output is correct
3 Correct 357 ms 1002208 KB Output is correct
4 Correct 358 ms 1002304 KB Output is correct
5 Correct 352 ms 1002336 KB Output is correct
6 Correct 360 ms 1002328 KB Output is correct
7 Correct 377 ms 1002232 KB Output is correct
8 Correct 366 ms 1002296 KB Output is correct
9 Correct 369 ms 1002240 KB Output is correct
10 Correct 362 ms 1002156 KB Output is correct
11 Incorrect 356 ms 1002188 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 370 ms 1002132 KB Output is correct
2 Correct 378 ms 1002232 KB Output is correct
3 Correct 418 ms 1002344 KB Output is correct
4 Correct 352 ms 1002352 KB Output is correct
5 Correct 357 ms 1002220 KB Output is correct
6 Correct 368 ms 1002176 KB Output is correct
7 Correct 355 ms 1002320 KB Output is correct
8 Correct 351 ms 1002276 KB Output is correct
9 Correct 384 ms 1002172 KB Output is correct
10 Correct 354 ms 1002236 KB Output is correct
11 Correct 357 ms 1002252 KB Output is correct
12 Correct 357 ms 1002180 KB Output is correct
13 Correct 379 ms 1002216 KB Output is correct
14 Correct 399 ms 1002208 KB Output is correct
15 Correct 353 ms 1002220 KB Output is correct
16 Correct 385 ms 1002228 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 1002224 KB Output is correct
2 Correct 358 ms 1002196 KB Output is correct
3 Correct 357 ms 1002208 KB Output is correct
4 Correct 358 ms 1002304 KB Output is correct
5 Correct 352 ms 1002336 KB Output is correct
6 Correct 360 ms 1002328 KB Output is correct
7 Correct 377 ms 1002232 KB Output is correct
8 Correct 366 ms 1002296 KB Output is correct
9 Correct 369 ms 1002240 KB Output is correct
10 Correct 362 ms 1002156 KB Output is correct
11 Incorrect 356 ms 1002188 KB Output isn't correct
12 Halted 0 ms 0 KB -