#include <bits/stdc++.h>
using namespace std;
using str = std::string;
template<typename _t> using vec = std::vector<_t>;
template<typename _t> using dbl = std::pair<_t, _t>;
using ll = long long;
using sz = size_t;
#define _mp make_pair
#define _mt make_tuple
#define _f first
#define _s second
#define _ot cout <<
#define _in cin >>
#define _er cerr <<
#define _p << ' ' <<
#define _nl '\n'
#define _el << _nl
#define _rg(i, s, e) for (auto i = s; i < e; ++i)
#define _up(i, e) _rg(i, 0, e)
#define _dn(i, s, e) for (auto i = s; i > e; --i)
#define _fr(i, s, e, j) for (auto i = s; i < e; i += j)
#define _elif else if
#define _fn auto
#define _var auto
#define _cexpr constexpr
_cexpr sz _max_n = 100*1024, _max_m = 100*1024;
int n, m;
dbl<ll> p[_max_n];
ll c[_max_m];
ll dp[2][_max_n+1];
_fn main() -> int {
iostream::sync_with_stdio(false);
cin.tie(0);
memset(dp[0], 0, sizeof(dp[0][0])*(n+1));
_in n >> m;
_up(i, n) {
static int s, v;
_in s >> v;
p[i] = _mp(v, s);
}
sort(p, p+n);
//_er 'p'; _up(i, n) _er "" _p '<' _p p[i]._f _p ',' _p p[i]._s _p '>'; _er _nl;
_up(i, m) {
_in c[i];
}
sort(c, c+m);
//_er 'f'; _up(i, m) _er "" _p c[i]; _er _nl;
_up(i, m) {
dp[1][0] = 0;
//_er "Frame #" << i _p ':' _p c[i] _el;
_up(j, n) {
//_er "Painting #" << j _p ':' _p p[j]._s _el;
dp[1][j+1] = dp[1][j];
//_er "Prev result =" _p dp[1][j] _el;
//_er "Prev frame =" _p dp[0][j] _el;
if (p[j]._s <= c[i]) {
dp[1][j+1] = max(dp[1][j+1], dp[0][j]+1);
}
//_er "This result =" _p dp[1][j+1] _el;
}
//_er ":0"; _up(j, n+1) _er "" _p dp[0][j]; _er _nl;
//_er ":1"; _up(j, n+1) _er "" _p dp[1][j]; _er _nl;
swap(dp[0], dp[1]);
}
_ot dp[0][m] _el;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
1876 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
1876 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
1876 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
