oj.uz

Submission #786131

# Submission time Handle Problem Language Result Execution time Memory
786131 2023-07-18T04:24:38 Z kebine Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 212 KB 
#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){ // boleh masuk
                    // 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){ // kecilin batas
                    dp[i][j].se = min(sv[i].se, dp[i-1][j].se);
                }
            }
            else{
                if(dp[i][j-1].fi>dp[i][j].fi){
                    dp[i][j]=dp[i][j-1];
                }
                else if(dp[i][j].fi==dp[i][j-1].fi){
                    dp[i][j].se = min(dp[i][j].se,dp[i][j-1].se);
                }
            }
            // cout<<dp[i][j].fi<<' '<<dp[i][j].se<<"		";
        }
        // cout<<'\n';
    }

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


    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -