oj.uz

답안 #127982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127982 2019-07-10T09:47:43 Z 구재현(#3116) AAQQZ (JOI15_aaqqz) C++14
10 / 100
 4000 ms 572 KB 
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 3005;

int n, c, a[MAXN];

struct ds{
	int cnt[MAXN], zeroes;
	void init(){
		memset(cnt, 0, sizeof(cnt));
		zeroes = c + 1;
	}
	void add(int x, int v){
		if(cnt[x] == 0) zeroes--;
		cnt[x] += v;
		if(cnt[x] == 0) zeroes++;
	}
	int query(){ return zeroes; }
}ds;

int f(int x, int y){
	int ret = 0;
	while(x >= 0 && y < n && a[x] == a[y]){
		x--;
		y++;
		ret++;
	}
	return 2 * ret;
}

int lcp(vector<int> &s, vector<int> &t){
	for(int i=0; i<s.size(); i++){
		if(s[i] != t[i]) return i;
	}
	return s.size();
}

int solve(int x, int y, vector<int> F, vector<int> G, int ignore){
	ds.init();
	int ptr = 0, cnt = 0, ret = 0;
	vector<int> s, t;
	for(auto &i : G){
		if(i == ignore){
			cnt++;
			if(s == t) ret = max(ret, cnt + 2 * ptr + f(x - ptr, y + cnt + ptr));
			else ret = max(ret, cnt + 2 * lcp(s, t));
			continue;
		}
		if(ptr == F.size()){
			break;
		}
		s.push_back(F[ptr++]);
		t.push_back(i);
		sort(t.begin(), t.end());
		if(s == t) ret = max(ret, cnt + 2 * ptr + f(x - ptr, y + cnt + ptr));
		else ret = max(ret, cnt + 2 * lcp(s, t));
	}
	return ret;
}

int solve(){
	int ret = 0;
	for(int i=0; i<n; i++){
		int p = 0;
		while(i - p >= 0 && i + p < n && a[i - p] == a[i + p]) p++;
		vector<int> L, R;
		for(int j=i-p; j>=0; j--) L.push_back(a[j]);
		for(int j=i+p; j<n; j++) R.push_back(a[j]);
		ret = max(ret, 2 * p - 1 + solve(i - p, i + p, L, R, -1));
	}
	for(int i=1; i<n; i++){
		int p = 0;
		while(i - p - 1 >= 0 && i + p < n && a[i - p - 1] == a[i + p]) p++;
		vector<int> L, R;
		for(int j=i-p-1; j>=0; j--) L.push_back(a[j]);
		for(int j=i+p; j<n; j++) R.push_back(a[j]);
		ret = max(ret, 2 * p + solve(i - p - 1, i + p, L, R, -1));
	}
	for(int i=0; i<n-1; i++){
		int nxt = -1;
		for(int j=i+1; j<n; j++){
			if(a[i] > a[j]){
				nxt = j;
				break;
			}
		}
		if(nxt != -1){
			vector<int> L, R;
			for(int j=i; j>=0; j--) L.push_back(a[j]);
			for(int j=i+1; j<n; j++){
				R.push_back(a[j]);
			}
			ret = max(ret, solve(i, i + 1, L, R, a[nxt]));
		}
	}
	return ret;
}

int main(){
	int cnt[MAXN] = {};
	cin >> n >> c;
	for(int i=0; i<n; i++){
		cin >> a[i];
		cnt[a[i]]++;
	}
	int ret = *max_element(cnt, cnt + MAXN);
	ret = max(ret, solve());
	for(int i=0; i<n; i++) a[i] = c + 1 - a[i];
	reverse(a, a + n);
	ret = max(ret, solve());
	cout << ret << endl;
}

Compilation message

aaqqz.cpp: In function 'int lcp(std::vector<int>&, std::vector<int>&)':
aaqqz.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~
aaqqz.cpp: In function 'int solve(int, int, std::vector<int>, std::vector<int>, int)':
aaqqz.cpp:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr == F.size()){
      ~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 0 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 380 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 380 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 376 KB Output is correct
23 Correct 3 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 2 ms 508 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 3 ms 376 KB Output is correct
30 Correct 3 ms 376 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 2 ms 372 KB Output is correct
33 Correct 3 ms 376 KB Output is correct
34 Correct 3 ms 376 KB Output is correct
35 Correct 3 ms 376 KB Output is correct
36 Correct 3 ms 376 KB Output is correct
37 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 0 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 380 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 380 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 376 KB Output is correct
23 Correct 3 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 2 ms 508 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 3 ms 376 KB Output is correct
30 Correct 3 ms 376 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 2 ms 372 KB Output is correct
33 Correct 3 ms 376 KB Output is correct
34 Correct 3 ms 376 KB Output is correct
35 Correct 3 ms 376 KB Output is correct
36 Correct 3 ms 376 KB Output is correct
37 Correct 3 ms 376 KB Output is correct
38 Execution timed out 4097 ms 572 KB Time limit exceeded
39 Halted 0 ms 0 KB -