oj.uz

Submission #127940

# Submission time Handle Problem Language Result Execution time Memory
127940 2019-07-10T08:49:53 Z 구재현(#3116) JOI15_aaqqz (JOI15_aaqqz) C++14
0 / 100
 2 ms 376 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 solve(int x, int y, vector<int> F, vector<int> G, int ignore){
	for(int i=0; i+1<F.size(); i++){
		if(F[i] > F[i+1]){
			F.resize(i + 1);
			break;
		}
	}
	ds.init();
	int ptr = 0, cnt = 0, ret = 0;
	for(auto &i : G){
		if(i == ignore){
			cnt++;
			if(ds.query() == c + 1) ret = max(ret, cnt + 2 * ptr + f(x - ptr, y + cnt + ptr));
			continue;
		}
		if(ptr == F.size()){
			break;
		}
		ds.add(F[ptr], +1);
		ds.add(i, -1);
		ptr++;
		if(ds.query() == c + 1) ret = max(ret, cnt + 2 * ptr + f(x - ptr, y + cnt + ptr));
	}
	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++){
				if(a[j] < a[nxt]) break;
				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 solve(int, int, std::vector<int>, std::vector<int>, int)':
aaqqz.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i+1<F.size(); i++){
               ~~~^~~~~~~~~
aaqqz.cpp:48:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr == F.size()){
      ~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -