| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127891 |
2019-07-10T08:11:47 Z |
구재현(#3116) |
JOI15_aaqqz (JOI15_aaqqz) |
C++14 |
|
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 solve(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);
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);
}
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));
}
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));
}
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(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(std::vector<int>, std::vector<int>, int)':
aaqqz.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i+1<F.size(); i++){
~~~^~~~~~~~~
aaqqz.cpp:38:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ptr == F.size()){
~~~~^~~~~~~~~~~
| # |
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 |
- |
| # |
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 |
- |
