제출 #334551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334551		Tahmid690	Exhibition (JOI19_ho_t2)	C++14	0 / 100	3 ms	4204 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
using namespace std;
#define mx 100005
struct pic{
    int val,siz;
};
bool cmp(pic a,pic b){
    return a.siz<b.siz;
}
int n,m;
pic ara[mx];
int frames[mx];
int dp[100][100][100];
int DP(int nidx,int midx,int prev){
    
    if(nidx>=n || midx>=m) return 0;
    
    if(prev!=-1 && dp[nidx][midx][prev]!=-1) return dp[nidx][midx][prev];
    
    int ret;
    ret=DP(nidx+1,midx,prev);
    if(prev==-1 || ara[nidx].val>=ara[prev].val){
        int xo=midx;
        while(frames[xo]<ara[nidx].siz){
            xo++;
        }
        if(xo<m){
            ret=max(ret,1+DP(nidx+1,xo+1,nidx));
        }
    }
    //cout << nidx << " " << midx << " " << prev << " " << ret << endl;
    return dp[nidx][midx][prev]=ret;
}
int main(){
    cin >> n >> m;
    //cout << n << " " << m << endl;
    for(int i=0;i<n;i++) cin >> ara[i].siz >> ara[i].val;
    for(int i=0;i<m;i++) cin >> frames[i];
    sort(ara,ara+n,cmp);
    sort(frames,frames+m);
    memset(dp,-1,sizeof dp);
    cout << DP(0,0,-1) << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50