제출 #1321046

#제출 시각아이디문제언어결과실행 시간메모리
1321046yonatanlGym Badges (NOI22_gymbadges)C++20
15 / 100
2094 ms27636 KiB
#include <iostream>
#include <vector>
#include <algorithm>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

const ll INF = 1e18;

void solve() {
	ll n;
	cin >> n;
	vll l(n), r(n);
	rep(i, 0, n) cin >> l[i];
	rep(i, 0, n) cin >> r[i];
	vector<pair<ll, pll>> arr(n);
	rep(i, 0, n) {
		arr[i] = { r[i] + l[i], {l[i], i} };
	}
	sort(arr.begin(), arr.end());
	vpll dp(n, {-1, INF});
	dp[0] = { 1, l[arr[0].second.second] };
	ll ans = 1;
	rep(i, 1, n) {
		dp[i] = { 1, l[arr[i].second.second] };
		ll curL = l[arr[i].second.second];
		ll curR = r[arr[i].second.second];
		for (ll j = i - 1; j >= 0; j--) {
			if (dp[j].second <= curR) {
				if (dp[j].first + 1 > dp[i].first) {
					dp[i] = { dp[j].first + 1, dp[j].second + curL };
				}
				else if (dp[j].first + 1 == dp[i].first) {
					upmin(dp[i].second, curL + dp[j].second);
				}
			}
		}
		upmax(ans, dp[i].first);
	}
	cout << ans << endl;
}

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

	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...