Submission #752904

# Submission time Handle Problem Language Result Execution time Memory
752904 2023-06-04T08:37:48 Z the_programmer_of_python Exhibition (JOI19_ho_t2) C++11
0 / 100
3 ms 1876 KB
#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 -