QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54631#4191. Hectic Harbour IIT3alaadl3k2olyehymn3k#WA 2ms3740kbC++2.3kb2022-10-09 21:35:572022-10-09 21:35:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-09 21:35:58]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3740kb
  • [2022-10-09 21:35:57]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define gtr(T) vector<T>,greater<T>
#define int long long
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

void err(istream_iterator<string> it) {cerr << endl;}
template<typename T, typename... Args>void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << " = " << a << endl;err(++it, args...);}

using ll  = long long;
using pii = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vector<int>>;


const int dx[] = {0, 0, 1,  -1, 1, -1,  1, -1};
const int dy[] = {1 , -1, 0, 0, 1, -1, -1,  1};


const int N = 1e6 + 5;
const int M = 1e3 + 5;
const int MOD = 100;


signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, s1, s2;
    cin >> n >> s1 >> s2;
    bool flag = 0;
    deque<int> dq;
    for(int i = 0; i < s1; ++i){
        int x; cin >> x;
        dq.push_back(x);
        flag |= (x == 0);
    }
    vector<int> v;
    for(int i = 0; i < s2; ++i){
        int x; cin >> x;
        v.push_back(x);
    }
    if(flag){
        while(!v.empty()){
            dq.push_front(v.back());
            v.pop_back();
        }
    }else{
        for(int i = 0; i < sz(v); ++i)dq.push_back(v[i]);
    }
    int ans = 0;
    int idx = 0;
    for(int i = 0; i < sz(dq); ++i){
        if(dq[i] == 0){
            idx = i;
            break;
        }
    }
    int cur = 0;
    int i = idx + 1;
    vector<int> dp(n + 2);
    int mx = 0;
    while(i < sz(dq)){
        for(int j = idx; j < i; ++j){
            if(dq[j] < dq[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        mx = max(mx, dp[i]);
        i++;
    }
    i = idx - 1;
    ans += mx;
    mx = 0;
    while(i >= 0){
        for(int j = idx; j > i; --j){
            if(dq[j] < dq[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        mx = max(mx, dp[i]);
        --i;
    }
    ans += mx;
    cout << ans << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3572kb

input:

4 3 2
2 0 3
1 4

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

6 4 3
2 4 0 1
6 3 5

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

11 2 10
3 9
11 5 6 0 1 7 4 8 10 2

output:

6

result:

ok single line: '6'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

3 2 2
3 2
0 1

output:

3

result:

ok single line: '3'

Test #5:

score: -100
Wrong Answer
time: 2ms
memory: 3628kb

input:

7 4 4
0 6 3 1
5 7 2 4

output:

3

result:

wrong answer 1st lines differ - expected: '2', found: '3'