oj.uz

Submission #163494

# Submission time Handle Problem Language Result Execution time Memory
163494 2019-11-13T14:31:37 Z nvmdava Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 780460 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 405
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL

char c[N];
int dp[N][N][N][3];
int a[N];
vector<int> app[3];

int i[3];

int cost(int k, int r){
	i[k]--;
	int res = dp[i[0]][i[1]][i[2]][r];
	i[k]++;
	int v = app[k][i[k] - 1];
	int w = v;
	for(int j = 0; j < 3; j++){
		int a = lower_bound(app[j].begin(), app[j].end(), v) - app[j].begin();
		w += max(0, i[j] - a);
	}


	return res + abs(i[0] + i[1] + i[2] - w);
}

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

    int n;
    cin>>n;

    for(int i = 1; i <= n; i++){
    	cin>>c[i];
    	if(c[i] == 'R')
    		app[0].push_back(i);
    	else if(c[i] == 'G')
    		app[1].push_back(i);
    	else
    		app[2].push_back(i);
    }

    memset(dp, 0x3f, sizeof dp);

    for(i[0] = 0; i[0] <= app[0].size(); ++i[0]){
    	for(i[1] = 0; i[1] <= app[1].size(); ++i[1]){
    		for(i[2] = 0; i[2] <= app[2].size(); ++i[2]){
    			for(int k = 0; k < 3; ++k){
    				if(i[0] + i[1] + i[2] == 0){
    					dp[i[0]][i[1]][i[2]][k] = 0;
    				}
    				if(i[k] == 0) continue;
    				
    				for(int r = 0; r < 3; ++r){
    					if(k == r)
    						continue;
    					dp[i[0]][i[1]][i[2]][k] = min(dp[i[0]][i[1]][i[2]][k], cost(k, r));
    				}
    			}
    		}
    	}
    }
    int res = min(dp[app[0].size()][app[1].size()][app[2].size()][0], min(dp[app[0].size()][app[1].size()][app[2].size()][1], dp[app[0].size()][app[1].size()][app[2].size()][2]));
    if(res == 0x3f3f3f3f)
    	cout<<-1;
    else
    	cout<<res;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i[0] = 0; i[0] <= app[0].size(); ++i[0]){
                   ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:55:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(i[1] = 0; i[1] <= app[1].size(); ++i[1]){
                    ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(i[2] = 0; i[2] <= app[2].size(); ++i[2]){
                     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 821 ms 780428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 821 ms 780428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 669 ms 780460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 821 ms 780428 KB Time limit exceeded
2 Halted 0 ms 0 KB -