oj.uz

답안 #127935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127935 2019-07-10T08:44:36 Z 구재현(#3116) AAQQZ (JOI15_aaqqz) C++14
0 / 100
 7 ms 380 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 solve(vector<int> F, vector<int> G, int ignore, int maxsort){
	int ret = 0;
	for(int i=0; i<maxsort; i++){
		vector<int> w(G.begin(), G.begin() + i + 1);
		sort(w.rbegin(), w.rend());
		int tmp = 0;
		int cnt = 0;
		while(w.size() && w.back() == ignore) w.pop_back(), tmp++;
		reverse(w.begin(), w.end());
		for(int j=i+1; j<G.size(); j++) w.push_back(G[j]);
		for(int j=0; j<F.size() && j<w.size(); j++){
			if(F[j] != w[j]) break;
			cnt++;
		}
		if(cnt + tmp >= i) ret = max(ret, cnt * 2 + tmp);
	}
	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(L, R, -1, R.size()));
	}
	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(L, R, -1, R.size()));
	}
	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]);
			int maxsort = n - i - 1;
			for(int j=i+1; j<n; j++){
				R.push_back(a[j]);
			}
			ret = max(ret, solve(L, R, a[nxt], maxsort));
		}
	}
	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(std::vector<int>, std::vector<int>, int, int)':
aaqqz.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1; j<G.size(); j++) w.push_back(G[j]);
                  ~^~~~~~~~~
aaqqz.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<F.size() && j<w.size(); j++){
                ~^~~~~~~~~
aaqqz.cpp:33:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<F.size() && j<w.size(); j++){
                              ~^~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 380 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 6 ms 256 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 6 ms 256 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Incorrect 6 ms 372 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 380 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 6 ms 256 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 6 ms 256 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Incorrect 6 ms 372 KB Output isn't correct
9 Halted 0 ms 0 KB -