oj.uz

Submission #124152

# Submission time Handle Problem Language Result Execution time Memory
124152 2019-07-02T15:06:11 Z rajarshi_basu Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 331 ms 4344 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define vv vector
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int INF = 1e9;
const int MAXN = 400+5;
const int MAXK = 100+10;
// 0 = red, 1 = green, 2 = blue;
int dp[2][MAXN][MAXN][3]; // [index][redused][blueused][color of last cell] = min cost (blue used can be inferred)

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

   	int n;
   	string s;
   	FOR(i,2)FOR(j,MAXN)FOR(k,MAXN)FOR(l,3)dp[i][j][k][l] = INF;
   	cin >> n;
   	cin >> s;
   	vi r,g,b;
   	FOR(i,n){
   		switch(s[i]){
   			case 'R':r.pb(i);break;
   			case 'G':g.pb(i);break;
   			case 'Y':b.pb(i);break;
   		}
   	}
   	FOR(i,n){
   		FOR(j,MAXN)FOR(k,MAXN)FOR(l,3){
   			dp[0][j][k][l] = dp[1][j][k][l];
   			dp[1][j][k][l] = INF;
   		}
   		FOR(rr,r.size()+1){
   			FOR(gg,g.size()+1){
   				int bb = (i+1) - (rr+gg);
   				if(min(bb,min(rr,gg)) < 0 or bb > b.size())continue;
   				//cout << rr << " " << gg << " " << bb << endl;
   				
   				// try making this a red color cell;
   				if(rr > 0){
   					int cst = 0;
	   				if(i == 0){
	   					cst = 0;
	   				}else{
	   					cst = min(dp[1-1][rr-1][gg][1],dp[1-1][rr-1][gg][2]);
	   				}
	   				dp[1][rr][gg][0] = min(dp[1][rr][gg][0],abs(i-r[rr-1]) + cst);
	   			}
	   			// try for green
	   			if(gg > 0){
   					int cst = 0;
	   				if(i == 0){
	   					cst = 0;
	   				}else{
	   					cst = min(dp[1-1][rr][gg-1][0],dp[1-1][rr][gg-1][2]);
	   				}
	   				dp[1][rr][gg][1] = min(dp[1][rr][gg][1],abs(i-g[gg-1]) + cst);
	   			}
	   			// try for blue
	   			if(bb > 0){
   					int cst = 0;
	   				if(i == 0){
	   					cst = 0;
	   				}else{
	   					cst = min(dp[1-1][rr][gg][0],dp[1-1][rr][gg][1]);
	   				}
	   				dp[1][rr][gg][2] = min(dp[1][rr][gg][2],abs(i-b[bb-1]) + cst);
	   			}
   			}
   		}
   	}
   	int ans = INF;
   	FOR(k,3)ans = min(dp[1][r.size()][g.size()][k],ans);
   	if(ans >= INF){
   		cout << -1 << endl;
   	}else{
   		cout << ans/2 << endl;
   	}

    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:17:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
joi2019_ho_t3.cpp:63:10:
      FOR(rr,r.size()+1){
          ~~~~~~~~~~~~~         
joi2019_ho_t3.cpp:63:6: note: in expansion of macro 'FOR'
      FOR(rr,r.size()+1){
      ^~~
joi2019_ho_t3.cpp:17:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
joi2019_ho_t3.cpp:64:11:
       FOR(gg,g.size()+1){
           ~~~~~~~~~~~~~        
joi2019_ho_t3.cpp:64:7: note: in expansion of macro 'FOR'
       FOR(gg,g.size()+1){
       ^~~
joi2019_ho_t3.cpp:66:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        if(min(bb,min(rr,gg)) < 0 or bb > b.size())continue;
                                     ~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4228 KB Output is correct
2 Correct 7 ms 4216 KB Output is correct
3 Correct 7 ms 4216 KB Output is correct
4 Correct 13 ms 4232 KB Output is correct
5 Correct 16 ms 4188 KB Output is correct
6 Correct 16 ms 4260 KB Output is correct
7 Correct 16 ms 4220 KB Output is correct
8 Correct 16 ms 4216 KB Output is correct
9 Correct 16 ms 4216 KB Output is correct
10 Correct 14 ms 4216 KB Output is correct
11 Incorrect 16 ms 4220 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4228 KB Output is correct
2 Correct 7 ms 4216 KB Output is correct
3 Correct 7 ms 4216 KB Output is correct
4 Correct 13 ms 4232 KB Output is correct
5 Correct 16 ms 4188 KB Output is correct
6 Correct 16 ms 4260 KB Output is correct
7 Correct 16 ms 4220 KB Output is correct
8 Correct 16 ms 4216 KB Output is correct
9 Correct 16 ms 4216 KB Output is correct
10 Correct 14 ms 4216 KB Output is correct
11 Incorrect 16 ms 4220 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 7 ms 4216 KB Output is correct
2 Correct 322 ms 4236 KB Output is correct
3 Correct 319 ms 4236 KB Output is correct
4 Correct 320 ms 4216 KB Output is correct
5 Correct 318 ms 4232 KB Output is correct
6 Correct 319 ms 4232 KB Output is correct
7 Correct 319 ms 4232 KB Output is correct
8 Correct 319 ms 4244 KB Output is correct
9 Correct 316 ms 4188 KB Output is correct
10 Correct 331 ms 4216 KB Output is correct
11 Correct 318 ms 4240 KB Output is correct
12 Correct 161 ms 4344 KB Output is correct
13 Correct 210 ms 4344 KB Output is correct
14 Correct 256 ms 4216 KB Output is correct
15 Correct 318 ms 4216 KB Output is correct
16 Correct 326 ms 4216 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4228 KB Output is correct
2 Correct 7 ms 4216 KB Output is correct
3 Correct 7 ms 4216 KB Output is correct
4 Correct 13 ms 4232 KB Output is correct
5 Correct 16 ms 4188 KB Output is correct
6 Correct 16 ms 4260 KB Output is correct
7 Correct 16 ms 4220 KB Output is correct
8 Correct 16 ms 4216 KB Output is correct
9 Correct 16 ms 4216 KB Output is correct
10 Correct 14 ms 4216 KB Output is correct
11 Incorrect 16 ms 4220 KB Output isn't correct
12 Halted 0 ms 0 KB -