이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, K = 20;
#define pb push_back
int n, a[N], b[N], rmq[N][K];
map<int, vector<int>> m;
int subtask2(){
int ans = 0;
vector<bool> is_taken(n + 5, 0);
for(int i = 1; i <= n; i++){
if(a[i] == b[1]){
ans++;
int l = i-1, r = i + 1;
is_taken[i] = 1;
for(; l >= 1 && !is_taken[l] && a[l] < b[1]; l--) ans++, is_taken[l] = 1;
for(; r <= n && !is_taken[r] && a[r] < b[1]; r++) ans++, is_taken[r] = 1;
}
}
return ans;
}
int subtask4(){
// map<int, vector<int>> m;
// for(int i = 1; i <= n; i++) m[a[i]].pb(i);
// auto last_occ = [](int val, int pos){
// return upper_bound(m[val].begin(), m[val].end(), pos) - m[val].begin();
// };
// vector<int> dp(n + 5, 0);
// for(int i = 1; i <= n; i++){
// dp[i] = dp[i - 1];
// if(a[i] <= b[i]){
// int s = m[b[i]].size();
// if(s == 0) continue;
// int pos = last_occ(b[i], i);
// if(pos == 0) continue;
// pos--;
// dp[i] = max(dp[i], dp[pos - 1] + num_of_occ(b[i], pos, i));
// }
// }
int ans = 0;
//Will be completed.
return ans;
}
void precalc(){
for(int i = 1; i <= n; i++) rmq[i][0] = a[i];
for(int j = 1; j < K; j++){
for(int i = 1; i + (1<<j) <= n + 1; i++){
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j-1))][j - 1]);
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
precalc();
if(n > 5000){
bool is_b = 1;
for(int i = 2; i <= n; i++) if(b[i] != b[i - 1]) is_b = 0;
if(is_b){
cout << subtask2();
}else{
cout << subtask4();
}
return 0;
}
vector<vector<int>> occ(n + 2, vector<int>(n+2, 0));
vector<int> dp(n+3);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
occ[i][j] = occ[i][j - 1];
if(a[j] <= b[j] && b[j] == b[i]) occ[i][j]++;
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
dp[i] = dp[i - 1];
for(int j = 1; j <= i; j++){
int num = occ[i][i] - occ[i][j - 1];
dp[i] = max(dp[i], dp[j - 1] + num);
}
ans = max(ans, dp[i]);
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |