oj.uz

Submission #682488

# Submission time Handle Problem Language Result Execution time Memory
682488 2023-01-16T10:23:59 Z rila Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
100 / 100
 412 ms 888656 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 402;
int dp[MAXN][MAXN][MAXN][3];
int C[3][MAXN][MAXN][MAXN];//number of positions i have moved forward
int A[MAXN];
vector<int>V[3];
int where[3][MAXN];
int32_t main() 
{
	IAMSPEED
	int n; cin >> n;
	FOR(i,1,n) {
		char c; cin >> c;
		if(c=='R')A[i]=0;
		else if(c=='G')A[i]=1;
		else A[i]=2;
		V[A[i]].pb(i);
	}
	FOR(zz,0,2) {
		FOR(i,1,V[zz].size()) {

			int pos=V[zz][i-1];
			set<int> s;
			for(auto x:{0,1,2})s.insert(x);
			s.erase(zz);
			int c1=*s.begin(); s.erase(s.begin());
			int c2=*s.begin(); s.erase(s.begin());
			int cnt=0;
			FOR(xx,0,V[c1].size()) {
				int id1=0;
				if(xx)id1=V[c1][xx-1];
				if(id1>pos)++cnt;
				int st=cnt;
				FOR(yy,0,V[c2].size()) {
					int id2=0;
					if(yy)id2=V[c2][yy-1];
					if(id2>pos)++cnt;
					C[zz][i][xx][yy]=cnt;
				}
				cnt=st;
			}
		}
	}

	FOR(i,0,n)FOR(j,0,n)FOR(k,0,n)FOR(y,0,2)dp[i][j][k][y]=inf;
	dp[0][0][0][0]=0;
	dp[0][0][0][1]=0;
	dp[0][0][0][2]=0;
	FOR(i,0,V[0].size()) {
		FOR(j,0,V[1].size()){
			FOR(k,0,V[2].size()) {
				FOR(y,0,2) {
					int &cur=dp[i][j][k][y];
					if(cur==inf)continue;
					if(y!=0){ 
						if(i<V[0].size()){
							int curidx=C[0][i+1][j][k];

							chmin(dp[i+1][j][k][0], cur + curidx);
						}
					}
					if(y!=1) {
						if(j<V[1].size()) {
							int curidx=C[1][j+1][i][k];
							chmin(dp[i][j+1][k][1], cur + curidx);
						}
					} 
					if(y!=2){
						if(k<V[2].size()) {
							int curidx=C[2][k+1][i][j];
							chmin(dp[i][j][k+1][2], cur + curidx);
						}
					}
				}
			}
		}
	}
	int r=V[0].size();
	int g=V[1].size();
	int b=V[2].size();
	int ans = min({dp[r][g][b][0], dp[r][g][b][1], dp[r][g][b][2]});
	if(ans==inf)cout<<-1;
	else cout <<ans;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:96:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |       if(i<V[0].size()){
      |          ~^~~~~~~~~~~~
joi2019_ho_t3.cpp:103:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |       if(j<V[1].size()) {
      |          ~^~~~~~~~~~~~
joi2019_ho_t3.cpp:109:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |       if(k<V[2].size()) {
      |          ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1596 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 1 ms 1620 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1620 KB Output is correct
16 Correct 1 ms 1620 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1596 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 1 ms 1620 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1620 KB Output is correct
16 Correct 1 ms 1620 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 9 ms 20308 KB Output is correct
19 Correct 9 ms 20052 KB Output is correct
20 Correct 9 ms 20308 KB Output is correct
21 Correct 9 ms 20308 KB Output is correct
22 Correct 10 ms 20180 KB Output is correct
23 Correct 13 ms 20092 KB Output is correct
24 Correct 10 ms 19540 KB Output is correct
25 Correct 11 ms 20908 KB Output is correct
26 Correct 11 ms 21076 KB Output is correct
27 Correct 10 ms 20668 KB Output is correct
28 Correct 11 ms 20308 KB Output is correct
29 Correct 10 ms 20308 KB Output is correct
30 Correct 9 ms 20180 KB Output is correct
31 Correct 9 ms 19924 KB Output is correct
32 Correct 11 ms 20272 KB Output is correct
33 Correct 10 ms 20300 KB Output is correct
34 Correct 10 ms 20100 KB Output is correct
35 Correct 10 ms 19156 KB Output is correct
36 Correct 10 ms 19412 KB Output is correct
37 Correct 10 ms 17892 KB Output is correct
38 Correct 10 ms 20028 KB Output is correct
39 Correct 14 ms 20284 KB Output is correct
40 Correct 12 ms 17716 KB Output is correct
41 Correct 10 ms 19668 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 412 ms 888600 KB Output is correct
3 Correct 384 ms 884136 KB Output is correct
4 Correct 359 ms 888656 KB Output is correct
5 Correct 369 ms 888588 KB Output is correct
6 Correct 361 ms 888596 KB Output is correct
7 Correct 393 ms 884128 KB Output is correct
8 Correct 358 ms 884152 KB Output is correct
9 Correct 363 ms 879788 KB Output is correct
10 Correct 374 ms 888604 KB Output is correct
11 Correct 390 ms 888540 KB Output is correct
12 Correct 96 ms 237724 KB Output is correct
13 Correct 166 ms 418620 KB Output is correct
14 Correct 245 ms 605952 KB Output is correct
15 Correct 370 ms 888572 KB Output is correct
16 Correct 358 ms 888648 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1596 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 1 ms 1620 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1620 KB Output is correct
16 Correct 1 ms 1620 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 9 ms 20308 KB Output is correct
19 Correct 9 ms 20052 KB Output is correct
20 Correct 9 ms 20308 KB Output is correct
21 Correct 9 ms 20308 KB Output is correct
22 Correct 10 ms 20180 KB Output is correct
23 Correct 13 ms 20092 KB Output is correct
24 Correct 10 ms 19540 KB Output is correct
25 Correct 11 ms 20908 KB Output is correct
26 Correct 11 ms 21076 KB Output is correct
27 Correct 10 ms 20668 KB Output is correct
28 Correct 11 ms 20308 KB Output is correct
29 Correct 10 ms 20308 KB Output is correct
30 Correct 9 ms 20180 KB Output is correct
31 Correct 9 ms 19924 KB Output is correct
32 Correct 11 ms 20272 KB Output is correct
33 Correct 10 ms 20300 KB Output is correct
34 Correct 10 ms 20100 KB Output is correct
35 Correct 10 ms 19156 KB Output is correct
36 Correct 10 ms 19412 KB Output is correct
37 Correct 10 ms 17892 KB Output is correct
38 Correct 10 ms 20028 KB Output is correct
39 Correct 14 ms 20284 KB Output is correct
40 Correct 12 ms 17716 KB Output is correct
41 Correct 10 ms 19668 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 412 ms 888600 KB Output is correct
44 Correct 384 ms 884136 KB Output is correct
45 Correct 359 ms 888656 KB Output is correct
46 Correct 369 ms 888588 KB Output is correct
47 Correct 361 ms 888596 KB Output is correct
48 Correct 393 ms 884128 KB Output is correct
49 Correct 358 ms 884152 KB Output is correct
50 Correct 363 ms 879788 KB Output is correct
51 Correct 374 ms 888604 KB Output is correct
52 Correct 390 ms 888540 KB Output is correct
53 Correct 96 ms 237724 KB Output is correct
54 Correct 166 ms 418620 KB Output is correct
55 Correct 245 ms 605952 KB Output is correct
56 Correct 370 ms 888572 KB Output is correct
57 Correct 358 ms 888648 KB Output is correct
58 Correct 381 ms 841252 KB Output is correct
59 Correct 375 ms 852312 KB Output is correct
60 Correct 373 ms 841192 KB Output is correct
61 Correct 374 ms 842384 KB Output is correct
62 Correct 383 ms 886720 KB Output is correct
63 Correct 368 ms 886220 KB Output is correct
64 Correct 372 ms 878272 KB Output is correct
65 Correct 371 ms 864932 KB Output is correct
66 Correct 376 ms 835348 KB Output is correct
67 Correct 368 ms 840636 KB Output is correct
68 Correct 376 ms 844188 KB Output is correct
69 Correct 380 ms 847156 KB Output is correct
70 Correct 383 ms 849364 KB Output is correct
71 Correct 376 ms 845284 KB Output is correct
72 Correct 350 ms 818376 KB Output is correct
73 Correct 325 ms 766420 KB Output is correct