| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127971 |
2019-07-10T09:41:11 Z |
구재현(#3116) |
JOI15_aaqqz (JOI15_aaqqz) |
C++14 |
|
3 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 f(int x, int y){
int ret = 0;
while(x >= 0 && y < n && a[x] == a[y]){
x--;
y++;
ret++;
}
return 2 * ret;
}
int lcp(string &s, string &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;
string 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()){
break;
}
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(){
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++){
if(a[j] < a[nxt]) break;
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::__cxx11::string&, std::__cxx11::string&)':
aaqqz.cpp:34: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:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i+1<F.size(); i++){
~~~^~~~~~~~~
aaqqz.cpp:57:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ptr == F.size()){
~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 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 |
3 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
