oj.uz

Submission #334551

# Submission time Handle Problem Language Result Execution time Memory
334551 2020-12-09T11:39:13 Z Tahmid690 Exhibition (JOI19_ho_t2) C++14
0 / 100
 3 ms 4204 KB 
#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.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 50.0

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