Submission #786111

#	Time	Username	Problem	Language	Result	Execution time	Memory
786111		makanhulia	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	320 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second

ll n,m;
vector<ll> c;
vector<pair<ll,ll> > sv;

// value doesnt matter

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>n>>m;
    sv.resize(n+1); c.resize(m+1);
    for(int i=1;i<=n;i++){
        cin>>sv[i].fi>>sv[i].se;
    }
    sort(sv.begin(),sv.end());
    for(int i=1;i<=m;i++) cin>>c[i];
    sort(c.begin(),c.end());

    pair<ll,ll> dp[n+1][m+1];
    memset(dp,0,sizeof(dp));
    // cout<<dp[0][0].fi<<' '<<dp[0][0].se<<'\n';

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            // cout<<"ijfi("<<dp[i][j].fi<<','<<dp[i-1][j].fi<<") ";
            if(sv[i].fi<=c[j]){
                if(sv[i].se >= dp[i-1][j-1].se){
                    // cout<<":v ";
                    dp[i][j].fi = dp[i-1][j-1].fi + 1;
                    dp[i][j].se = sv[i].se;
                }
                if(dp[i][j].fi == dp[i-1][j].fi){
                    dp[i][j].se = min(sv[i].se, dp[i-1][j].se);
                }
            }
            // cout<<dp[i][j].fi<<' '<<dp[i][j].se<<'	';
        }
        // cout<<'\n';
    }

    cout<<dp[n][m].fi<<'\n';


    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50