oj.uz

Submission #128155

# Submission time Handle Problem Language Result Execution time Memory
128155 2019-07-10T13:16:14 Z 구재현(#3116) JOI15_aaqqz (JOI15_aaqqz) C++14
0 / 100
 44 ms 35832 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){
	assert(x <= 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;
		}
	}
	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:31: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:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i+1<F.size(); i++){
               ~~~^~~~~~~~~
aaqqz.cpp:54: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 35608 KB Output is correct
2 Correct 41 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 40 ms 35832 KB Output is correct
6 Correct 40 ms 35704 KB Output is correct
7 Correct 40 ms 35752 KB Output is correct
8 Correct 40 ms 35704 KB Output is correct
9 Correct 40 ms 35704 KB Output is correct
10 Correct 40 ms 35704 KB Output is correct
11 Correct 44 ms 35832 KB Output is correct
12 Incorrect 40 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 35608 KB Output is correct
2 Correct 41 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 40 ms 35832 KB Output is correct
6 Correct 40 ms 35704 KB Output is correct
7 Correct 40 ms 35752 KB Output is correct
8 Correct 40 ms 35704 KB Output is correct
9 Correct 40 ms 35704 KB Output is correct
10 Correct 40 ms 35704 KB Output is correct
11 Correct 44 ms 35832 KB Output is correct
12 Incorrect 40 ms 35704 KB Output isn't correct
13 Halted 0 ms 0 KB -