oj.uz

Submission #128151

# Submission time Handle Problem Language Result Execution time Memory
128151 2019-07-10T13:14:44 Z 구재현(#3116) JOI15_aaqqz (JOI15_aaqqz) C++14
0 / 100
 52 ms 35704 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];
int dp[MAXN][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){
	if(x < 0 || y >= n) return 0;
	return dp[x][y];
}

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){
	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;
	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()){
			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(){
	memset(dp, 0, sizeof(dp));
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(a[i] == a[j]) dp[i][j] = (i > 0 ? dp[i-1][j+1] : 0) + 1;
			else dp[i][j] = 0;
		}
	}

	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:30: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:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i+1<F.size(); i++){
               ~~~^~~~~~~~~
aaqqz.cpp:53: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 40 ms 35704 KB Output is correct
2 Correct 40 ms 35704 KB Output is correct
3 Correct 40 ms 35704 KB Output is correct
4 Correct 40 ms 35704 KB Output is correct
5 Correct 39 ms 35704 KB Output is correct
6 Correct 40 ms 35704 KB Output is correct
7 Correct 40 ms 35676 KB Output is correct
8 Correct 52 ms 35704 KB Output is correct
9 Correct 39 ms 35704 KB Output is correct
10 Correct 40 ms 35704 KB Output is correct
11 Correct 40 ms 35704 KB Output is correct
12 Incorrect 39 ms 35704 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35704 KB Output is correct
2 Correct 40 ms 35704 KB Output is correct
3 Correct 40 ms 35704 KB Output is correct
4 Correct 40 ms 35704 KB Output is correct
5 Correct 39 ms 35704 KB Output is correct
6 Correct 40 ms 35704 KB Output is correct
7 Correct 40 ms 35676 KB Output is correct
8 Correct 52 ms 35704 KB Output is correct
9 Correct 39 ms 35704 KB Output is correct
10 Correct 40 ms 35704 KB Output is correct
11 Correct 40 ms 35704 KB Output is correct
12 Incorrect 39 ms 35704 KB Output isn't correct
13 Halted 0 ms 0 KB -