Submission #786142

#	Time	Username	Problem	Language	Result	Execution time	Memory
786142		kebine	Exhibition (JOI19_ho_t2)	C++17	0 / 100	9 ms	23956 KiB

joi2019_ho_t2

#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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50