oj.uz

Submission #786142

# Submission time Handle Problem Language Result Execution time Memory
786142 2023-07-18T04:48:48 Z kebine Exhibition (JOI19_ho_t2) C++17
0 / 100
 9 ms 23956 KB 
#include <bits/stdc++.h>
using namespace std;

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

bool sorting(pair<int, int> a, pair<int, int> b) {return b.sec > a.sec;}

int n, m; 
pair<int, int> num[1005];
int dp[1005][1005][3];
int sizes[1005];

int dpalgo(int idxn, int idxm, bool yes) {
    // cerr << idxn << " " << idxm << " " << yes << endl;
    if(idxn == n+1) return 0;
    if(idxm == m+1) return 0;
    if(dp[idxn][idxm][yes] != -1) return dp[idxn][idxm][yes];

    int ans = 0;
    ans = max(ans, dpalgo(idxn+1, idxm, yes));
    ans = max(ans, dpalgo(idxn, idxm+1, 0));
    if(num[idxn].fir <= sizes[idxm]) {
        if(yes) {
            if(sizes[idxm] >= sizes[idxm-1]) ans = max(ans, dpalgo(idxn+1, idxm+1, 1)+1);
        }
        else ans = max(ans, dpalgo(idxn+1, idxm+1, 1)+1);
    } 

    // cerr << idxn << " " << idxm << " " << yes << " " << ans << endl;
    return dp[idxn][idxm][yes] = ans;
}

void solve() {
    cin >> n >> m;


    for(int i = 1; i<=n; i++) cin >> num[i].fir >> num[i].sec;

    sort(num+1, num+n+1, sorting);

    
    // for(int i = 1; i<=n; i++) cout << num[i].fir << " " << num[i].sec << endl;

    memset(dp, -1, sizeof(dp));


    for(int i = 1; i<=m; i++) {
        cin >> sizes[i];
    }

    cout << dpalgo(1, 1, 0) << endl;

}

signed main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 50.0

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