| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127982 |
2019-07-10T09:47:43 Z |
구재현(#3116) |
JOI15_aaqqz (JOI15_aaqqz) |
C++14 |
|
4000 ms |
572 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(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){
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()){
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++){
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: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:51: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 |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
0 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
3 ms |
376 KB |
Output is correct |
| 10 |
Correct |
3 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
3 ms |
376 KB |
Output is correct |
| 13 |
Correct |
3 ms |
380 KB |
Output is correct |
| 14 |
Correct |
3 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
376 KB |
Output is correct |
| 16 |
Correct |
3 ms |
380 KB |
Output is correct |
| 17 |
Correct |
3 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
3 ms |
376 KB |
Output is correct |
| 20 |
Correct |
3 ms |
376 KB |
Output is correct |
| 21 |
Correct |
3 ms |
376 KB |
Output is correct |
| 22 |
Correct |
3 ms |
376 KB |
Output is correct |
| 23 |
Correct |
3 ms |
376 KB |
Output is correct |
| 24 |
Correct |
3 ms |
376 KB |
Output is correct |
| 25 |
Correct |
3 ms |
376 KB |
Output is correct |
| 26 |
Correct |
3 ms |
376 KB |
Output is correct |
| 27 |
Correct |
2 ms |
508 KB |
Output is correct |
| 28 |
Correct |
2 ms |
376 KB |
Output is correct |
| 29 |
Correct |
3 ms |
376 KB |
Output is correct |
| 30 |
Correct |
3 ms |
376 KB |
Output is correct |
| 31 |
Correct |
3 ms |
376 KB |
Output is correct |
| 32 |
Correct |
2 ms |
372 KB |
Output is correct |
| 33 |
Correct |
3 ms |
376 KB |
Output is correct |
| 34 |
Correct |
3 ms |
376 KB |
Output is correct |
| 35 |
Correct |
3 ms |
376 KB |
Output is correct |
| 36 |
Correct |
3 ms |
376 KB |
Output is correct |
| 37 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
0 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
3 ms |
376 KB |
Output is correct |
| 10 |
Correct |
3 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
3 ms |
376 KB |
Output is correct |
| 13 |
Correct |
3 ms |
380 KB |
Output is correct |
| 14 |
Correct |
3 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
376 KB |
Output is correct |
| 16 |
Correct |
3 ms |
380 KB |
Output is correct |
| 17 |
Correct |
3 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
3 ms |
376 KB |
Output is correct |
| 20 |
Correct |
3 ms |
376 KB |
Output is correct |
| 21 |
Correct |
3 ms |
376 KB |
Output is correct |
| 22 |
Correct |
3 ms |
376 KB |
Output is correct |
| 23 |
Correct |
3 ms |
376 KB |
Output is correct |
| 24 |
Correct |
3 ms |
376 KB |
Output is correct |
| 25 |
Correct |
3 ms |
376 KB |
Output is correct |
| 26 |
Correct |
3 ms |
376 KB |
Output is correct |
| 27 |
Correct |
2 ms |
508 KB |
Output is correct |
| 28 |
Correct |
2 ms |
376 KB |
Output is correct |
| 29 |
Correct |
3 ms |
376 KB |
Output is correct |
| 30 |
Correct |
3 ms |
376 KB |
Output is correct |
| 31 |
Correct |
3 ms |
376 KB |
Output is correct |
| 32 |
Correct |
2 ms |
372 KB |
Output is correct |
| 33 |
Correct |
3 ms |
376 KB |
Output is correct |
| 34 |
Correct |
3 ms |
376 KB |
Output is correct |
| 35 |
Correct |
3 ms |
376 KB |
Output is correct |
| 36 |
Correct |
3 ms |
376 KB |
Output is correct |
| 37 |
Correct |
3 ms |
376 KB |
Output is correct |
| 38 |
Execution timed out |
4097 ms |
572 KB |
Time limit exceeded |
| 39 |
Halted |
0 ms |
0 KB |
- |
