oj.uz

Submission #786163

# Submission time Handle Problem Language Result Execution time Memory
786163 2023-07-18T05:02:11 Z andecaandeci Exhibition (JOI19_ho_t2) C++17
0 / 100
 4 ms 8148 KB 
# include <bits/stdc++.h>
# define int long long
# define vi vector<int>
# define pb push_back
# define pii pair<int, int>
# define fi first
# define se second
# define endl '\n'
# define jess ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n, m, x[100005], memo[1005][1005];
pii a[100005];
vi v;

bool comp(pii a, pii b) {
    if(a.fi<b.fi) return 1;
    if(a.fi>b.fi) return 0;
    if(a.se<b.se) return 1;
    return 0;
}

int dp(int idx, int prev) {
    if(idx>n) return 0;
    if(memo[idx][prev]!=-1) return memo[idx][prev];
    int best=dp(idx+1, prev);
    if(v[idx]>=v[prev]) {
        best=max(best, dp(idx+1, idx)+1);
    }
    return memo[idx][prev]=best;
}

void solve() {
    memset(memo, -1, sizeof(memo));
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a+1, a+n+1);
    for(int i=1; i<=m; i++) {
        cin >> x[i];
    }
    sort(x+1, x+m+1);
    v.pb(0);
    for(int i=1; i<=m; i++) {
        int mni=1e9, idx;
        for(int j=1; j<=n; j++) {
            // cout << "aj wkw " << j << " : " << a[j].fi << " " << a[j].se << " " << mni << " " << x[i] << endl;
            if(a[j].fi <= x[i]) {
                if(a[j].se<=mni) {
                    mni=a[j].se;
                    idx=j;
                }
            } else break;
        }
        if(mni==1e9) continue;
        else {
            v.pb(mni);
            a[idx].se=1e9;
        }
    } 
    if(v.size()==1) {
        cout << 0 << endl;
        return;
    }
    cout << dp(1, 0) << endl;
    // ans.pb(v.back());
    // for(int i=1; i<v.size(); i++) {
    //     if(v[i]>=ans.back()) {
    //         ans.pb(v[i]);
    //     } else {
    //         int low=lower_bound(ans.begin(), ans.end(), v[i]) - ans.begin();
    //         ans[low]=v[i];
    //     }
    // }
}
 
signed main() {
    solve();
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 50.0

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