oj.uz

Submission #682489

# Submission time Handle Problem Language Result Execution time Memory
682489 2023-01-16T10:25:20 Z kym Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
100 / 100
 428 ms 888792 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 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 852 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 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 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 2 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 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 852 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 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 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 2 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 20332 KB Output is correct
19 Correct 10 ms 20068 KB Output is correct
20 Correct 9 ms 20408 KB Output is correct
21 Correct 11 ms 20308 KB Output is correct
22 Correct 10 ms 20184 KB Output is correct
23 Correct 8 ms 20052 KB Output is correct
24 Correct 8 ms 19524 KB Output is correct
25 Correct 10 ms 20948 KB Output is correct
26 Correct 9 ms 21076 KB Output is correct
27 Correct 9 ms 20696 KB Output is correct
28 Correct 9 ms 20308 KB Output is correct
29 Correct 9 ms 20308 KB Output is correct
30 Correct 9 ms 20180 KB Output is correct
31 Correct 11 ms 19924 KB Output is correct
32 Correct 9 ms 20180 KB Output is correct
33 Correct 9 ms 20320 KB Output is correct
34 Correct 9 ms 20124 KB Output is correct
35 Correct 8 ms 19156 KB Output is correct
36 Correct 8 ms 19412 KB Output is correct
37 Correct 8 ms 17876 KB Output is correct
38 Correct 8 ms 19924 KB Output is correct
39 Correct 8 ms 20180 KB Output is correct
40 Correct 8 ms 17720 KB Output is correct
41 Correct 8 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 365 ms 888588 KB Output is correct
3 Correct 428 ms 884232 KB Output is correct
4 Correct 359 ms 888560 KB Output is correct
5 Correct 363 ms 888584 KB Output is correct
6 Correct 362 ms 888652 KB Output is correct
7 Correct 362 ms 884168 KB Output is correct
8 Correct 364 ms 884316 KB Output is correct
9 Correct 370 ms 879736 KB Output is correct
10 Correct 370 ms 888656 KB Output is correct
11 Correct 372 ms 888588 KB Output is correct
12 Correct 102 ms 237616 KB Output is correct
13 Correct 166 ms 418656 KB Output is correct
14 Correct 246 ms 605960 KB Output is correct
15 Correct 370 ms 888792 KB Output is correct
16 Correct 374 ms 888652 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 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 852 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 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 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 2 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 20332 KB Output is correct
19 Correct 10 ms 20068 KB Output is correct
20 Correct 9 ms 20408 KB Output is correct
21 Correct 11 ms 20308 KB Output is correct
22 Correct 10 ms 20184 KB Output is correct
23 Correct 8 ms 20052 KB Output is correct
24 Correct 8 ms 19524 KB Output is correct
25 Correct 10 ms 20948 KB Output is correct
26 Correct 9 ms 21076 KB Output is correct
27 Correct 9 ms 20696 KB Output is correct
28 Correct 9 ms 20308 KB Output is correct
29 Correct 9 ms 20308 KB Output is correct
30 Correct 9 ms 20180 KB Output is correct
31 Correct 11 ms 19924 KB Output is correct
32 Correct 9 ms 20180 KB Output is correct
33 Correct 9 ms 20320 KB Output is correct
34 Correct 9 ms 20124 KB Output is correct
35 Correct 8 ms 19156 KB Output is correct
36 Correct 8 ms 19412 KB Output is correct
37 Correct 8 ms 17876 KB Output is correct
38 Correct 8 ms 19924 KB Output is correct
39 Correct 8 ms 20180 KB Output is correct
40 Correct 8 ms 17720 KB Output is correct
41 Correct 8 ms 19668 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 365 ms 888588 KB Output is correct
44 Correct 428 ms 884232 KB Output is correct
45 Correct 359 ms 888560 KB Output is correct
46 Correct 363 ms 888584 KB Output is correct
47 Correct 362 ms 888652 KB Output is correct
48 Correct 362 ms 884168 KB Output is correct
49 Correct 364 ms 884316 KB Output is correct
50 Correct 370 ms 879736 KB Output is correct
51 Correct 370 ms 888656 KB Output is correct
52 Correct 372 ms 888588 KB Output is correct
53 Correct 102 ms 237616 KB Output is correct
54 Correct 166 ms 418656 KB Output is correct
55 Correct 246 ms 605960 KB Output is correct
56 Correct 370 ms 888792 KB Output is correct
57 Correct 374 ms 888652 KB Output is correct
58 Correct 393 ms 841228 KB Output is correct
59 Correct 391 ms 852248 KB Output is correct
60 Correct 374 ms 841096 KB Output is correct
61 Correct 379 ms 842372 KB Output is correct
62 Correct 362 ms 886716 KB Output is correct
63 Correct 380 ms 886092 KB Output is correct
64 Correct 391 ms 878124 KB Output is correct
65 Correct 371 ms 864972 KB Output is correct
66 Correct 385 ms 835276 KB Output is correct
67 Correct 390 ms 840600 KB Output is correct
68 Correct 382 ms 844196 KB Output is correct
69 Correct 387 ms 847076 KB Output is correct
70 Correct 401 ms 849244 KB Output is correct
71 Correct 376 ms 845188 KB Output is correct
72 Correct 337 ms 818296 KB Output is correct
73 Correct 357 ms 766392 KB Output is correct