oj.uz

Submission #98252

# Submission time Handle Problem Language Result Execution time Memory
98252 2019-02-21T17:13:33 Z scanhex Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 774732 KB 
#include <bits/stdc++.h>

using namespace std;
using nagai = long long;
#define sz(x) int((x).size())

vector<int>occ[3];
const int N=404;
int dp[N][N][N][3];
#define chmi(x,y) x=min(x,y)
const int oo=0x3f3f3f3f;

int prec[3][3][N][N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	string s;
	cin>>s;
	for(int i=0;i<n;++i){
		if(s[i]=='R')occ[0].push_back(i);
		if(s[i]=='G')occ[1].push_back(i);
		if(s[i]=='Y')occ[2].push_back(i);
	}
	memset(dp,0x3f,sizeof dp);
	dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
			for(int k=0;k<occ[i].size();++k)
				for(int l=0;l<occ[j].size();++l){
					for(int kek=l;kek<occ[j].size();++kek)
						if(occ[j][kek]<occ[i][k])++prec[i][j][k][l];
				}
	int arr[3];
	int ans=oo;
	for(arr[0]=0;arr[0]<=occ[0].size();++arr[0])
		for(arr[1]=0;arr[1]<=occ[1].size();++arr[1])
			for(arr[2]=0;arr[2]<=occ[2].size();++arr[2])
				for(int last=0;last<3;++last){
					int lol=dp[arr[0]][arr[1]][arr[2]][last];
//					if(lol!=oo)
//						cerr<<arr[0]<<' '<<arr[1]<<' '<<arr[2]<<' '<<last<<' '<<lol<<'\n';
					if(arr[0]==occ[0].size()&&arr[1]==occ[1].size()&&arr[2]==occ[2].size())
						ans=min(ans,lol);
					for(int nw=0;nw<3;++nw){
						if(nw==last)continue;
						if(arr[nw]==occ[nw].size())continue;
						int cost=0;
						for(int x=0;x<3;++x)
							cost+=prec[nw][x][arr[nw]][arr[x]];
						arr[nw]++;
						chmi(dp[arr[0]][arr[1]][arr[2]][nw],lol+cost);
						arr[nw]--;
					}
				}
	if(ans==oo)ans=-1;
	cout<<ans<<'\n';
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<occ[i].size();++k)
                ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int l=0;l<occ[j].size();++l){
                 ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int kek=l;kek<occ[j].size();++kek)
                    ~~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(arr[0]=0;arr[0]<=occ[0].size();++arr[0])
               ~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(arr[1]=0;arr[1]<=occ[1].size();++arr[1])
                ~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(arr[2]=0;arr[2]<=occ[2].size();++arr[2])
                 ~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(arr[0]==occ[0].size()&&arr[1]==occ[1].size()&&arr[2]==occ[2].size())
         ~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(arr[0]==occ[0].size()&&arr[1]==occ[1].size()&&arr[2]==occ[2].size())
                                ~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(arr[0]==occ[0].size()&&arr[1]==occ[1].size()&&arr[2]==occ[2].size())
                                                       ~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(arr[nw]==occ[nw].size())continue;
          ~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 847 ms 774732 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 847 ms 774732 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 606 ms 774620 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 847 ms 774732 KB Time limit exceeded
2 Halted 0 ms 0 KB -