Submission #1301436

#TimeUsernameProblemLanguageResultExecution timeMemory
1301436tunademayoExhibition (JOI19_ho_t2)C++20
50 / 100
21 ms4424 KiB
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second

const bool Multitest = 0;
const int N = 1e5 + 10;

pair<int, int> a[N]; int b[N];
int n, m;
void maximize(int& a, int b)
{
    if(a < b) a = b;
}

namespace sub1
{
    const int Nsub = 1e3 + 10;

    int dp[Nsub][Nsub];

    void solve()
    {
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + m);

        for(int i = 1 ; i <= m ; i++)
        {
            for(int j = 1 ; j <= n ; j++)
            {
                dp[i][j] = dp[i - 1][j - 1] + (a[j].se <= b[i]);

                maximize(dp[i][j], dp[i][j - 1]);
            }
        }

        cout << dp[m][n];
    }
}

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

    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i].se >> a[i].fi;
    }

    for(int i = 1 ; i <= m ; i++) cin >> b[i];

    if(n <= 1000 && m <= 1000) sub1::solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int q = 1;

    if(Multitest)   cin >> q;

    while(q--) work();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...