Submission #833587

#	Time	Username	Problem	Language	Result	Execution time	Memory
833587		vjudge1	Exam (eJOI20_exam)	C++17	14 / 100	661 ms	524288 KiB

exam

#include<bits/stdc++.h>
using namespace std;
 int n;
vector<int> h(100002), t(100002);
map<pair<int, vector<int>>, int> m;
int dp(int i, vector<int> v){
    if(i == n) return 0;
    if(m.count({i, v})>0) return m[{i, v}];

    int best=dp(i+1, v);
    vector<int> temp=v;
    for(int j=i; j<n; j++){
        if(v[j] > t[i]) break;
        if(v[j] == t[i]){
            while(j>i){
                v[j]=t[i];
                j--;
            }
            best=max(best, dp(i+1, v)+1);
            break;
        }
    }
    v=temp;
    for(int j=i; j>=0; j--){
        if(v[j] > t[i]) break;
        if(v[j] == t[i]){
            while(j<i){
                v[j]=t[i];
                j++;
            }
            best=max(best, dp(i+1, v)+1);
            break;
        }
    }
    m[{i, temp}]=best;
    return best;
}
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>h[i];
    }
    for(int j=0; j<n; j++){
        cin>>t[j];
    }

    cout<<dp(0, h);
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22