| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127934 |
2019-07-10T08:43:37 Z |
구재현(#3116) |
JOI15_aaqqz (JOI15_aaqqz) |
C++14 |
|
5 ms |
408 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++){
if(a[j] < a[nxt]){
maxsort = min(maxsort, j - i - 1);
break;
}
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++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
408 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| 5 |
Correct |
4 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
408 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| 5 |
Correct |
4 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
