제출 #1122292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122292		Ryu	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	504 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#define sts(v) stable_sort(v.BE, v.E)
#define Rsts(v) stable_sort(v.rBE, v.rE)
#define rev(v) reverse(v.BE, v.E)
#define BE begin()
#define rBE rbegin()
#define E end()
#define rE rend()
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define F first
#define S second
    
using namespace std;
using ll = long long;
using T = pair<ll, ll>;
const int M = 998244353;

struct ABI{
    vector<pair<int, int>> abi;
    ABI(int n){
        abi.resize(n + 1);
    }
    void updt(int ini, int val){
        for(int i = ini; i < (int)abi.size(); i += i & -i){
            if(abi[i].F < val)
                abi[i] = {val, ini};
            else if(abi[i].F == val)
                abi[i].S = min(ini, abi[i].S);
        }
            
    }
    pair<int, int> query(int i){
        pair<int, int> ans = {0, 0};
        for(; i > 0; i -= i & -i)
            if(ans.F < abi[i].F)
                ans = abi[i];
        return ans;
    }
};

int bs(vector<int> &v, int val) {
    int l = 1, r = v.size() - 1, ans = -1;

    while(l < r) {
        int m = (l + r) / 2;

        if(v[m] <= val) l = m + 1, ans = m;
        else r = m - 1;
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    
    // st para guardar la respuesta en la caja i
    // dp[i] = query(1, n - 1)

    int n, m; cin >> n >> m;
    vector<pair<int, int>> v(n + 1, {INT_MIN, INT_MIN});
    vector<int> F(m + 1, INT_MIN);
    for(int i = 1; i <= n; i++){
        int w, val; cin >> w >> val;

        v[i] = {val, w};
    }
    for(int i = 1; i <= m; i++)
        cin >> F[i];

    sts(F);
    sts(v);
    

    int res = 0;
    ABI abi(m);

    vector<pair<int, int>> dp(n + 1, {0, 0});
    dp[0] = {0, 0};
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m && !dp[i].S; j++)
            if(v[i].S <= F[j])dp[i].S = j;
        
        if(!dp[i].S)continue;
        
        for(int j = 1; j < i; j++){
            if(dp[j].S != m){
                if(dp[j].F + 1 > dp[i].F)dp[i] = {dp[j].F + 1, max(dp[i].S, dp[j].S + 1)};
                else if(dp[j].F == dp[i].F)dp[i].S = min(dp[i].S, dp[j].S);
            }
        }
            

        if(!dp[i].F)dp[i].F = 1;
        res = max(res, dp[i].F);
    }

    cout << res;

    return 0;
}

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