oj.uz

Submission #786111

# Submission time Handle Problem Language Result Execution time Memory
786111 2023-07-18T04:00:43 Z makanhulia Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 320 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){
                    // 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 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 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 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 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -