oj.uz

답안 #209211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
209211 2020-03-13T12:30:39 Z kostia244 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 780388 KB 
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,fma,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int maxn = 405;
void minq(int &a, int b) {
	if(a > b) a = b;
}
int dp[maxn][maxn][maxn][3];
int n;
string s;
vi p[3];
int id(char c) {
	if(c=='R') return 0;
	if(c=='G') return 1;
	return 2;
}
inline int cost(int i, int j, int k, int l, int w) {
	if(l == w) return 1<<20;
	int c, n1, n2;
	if(w==0) {
		c = 0;
		n1 = 1;
		n2 = 2;
	}
	if(w==1) {// i, j, k => j i k
		swap(i, j);
		c = 1;
		n1 = 0;
		n2 = 2;
	}
	if(w==2) {// i, j, k => k, j, i
		swap(i, k);
		c = 2;
		n1 = 1;
		n2 = 0;
	}
	if(p[c].size()<=i) return 1<<20;
	int ans = p[c][i] - i;
	int t, z;
	for(t = 0, z = 1<<9; z>>=1;)
		if(t+z<p[n1].size()&&p[n1][t+z]<p[c][i]) t+=z;
	if(p[n1].size()&&p[n1][0]<p[c][i])
		ans -= min(t+1, j);
	for(t = 0, z = 1<<9; z>>=1;)
		if(t+z<p[n2].size()&&p[n2][t+z]<p[c][i]) t+=z;
	if(p[n2].size()&&p[n2][0]<p[c][i])
		ans -= min(t+1, k);
	return ans;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	for(int i = 0; i < n; i++) p[id(s[i])].pb(i);
	memset(dp, 0x3f, sizeof dp);
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	int ans = 1<<30;
	#pragma GCC ignvd
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			for(int k = 0; k <= n; k++) {
				for(int l = 0; l < 3; l++) {
					if(i+j+k==n) ans = min(ans, dp[i][j][k][l]);
					if(dp[i][j][k][l]>n*n) continue;
					minq(dp[i+1][j][k][0], dp[i][j][k][l] + cost(i, j, k, l, 0));
					minq(dp[i][j+1][k][1], dp[i][j][k][l] + cost(i, j, k, l, 1));
					minq(dp[i][j][k+1][2], dp[i][j][k][l] + cost(i, j, k, l, 2));
				}
			}
		}
	}
	if(ans>n*n) ans = -1;
	cout << ans;
}

Compilation message

joi2019_ho_t3.cpp:65:0: warning: ignoring #pragma GCC ignvd [-Wunknown-pragmas]
  #pragma GCC ignvd
 
joi2019_ho_t3.cpp: In function 'int cost(int, int, int, int, int)':
joi2019_ho_t3.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(p[c].size()<=i) return 1<<20;
     ~~~~~~~~~~~^~~
joi2019_ho_t3.cpp:48:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(t+z<p[n1].size()&&p[n1][t+z]<p[c][i]) t+=z;
      ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:52:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(t+z<p[n2].size()&&p[n2][t+z]<p[c][i]) t+=z;
      ~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 615 ms 780360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 615 ms 780360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 411 ms 780280 KB Output is correct
2 Execution timed out 690 ms 780388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 615 ms 780360 KB Time limit exceeded
2 Halted 0 ms 0 KB -