Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(l) cerr<<" smotri huinyi : "<<#l<<' '<<l<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- typedef long long ll;
- typedef long double ld;
- const int N = 3e5 + 1;
- ll dp[N][4];
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- srand(time(NULL));
- ll w1, h1, n;
- cin >> w1 >> h1 >> n;
- vector<ll> w(n), h(n);
- vector<vector<ll>> dp(w1 + 1, vector<ll>(h1 + 1, 0));
- for (ll i = 0; i < n; i++) {
- cin >> w[i] >> h[i];
- }
- const ll inf = 1e18;
- vector<vector<ll>> pref_mx(w1 + 1, vector<ll>(h1 + 1, -inf));
- for (ll l = 1; l <= w1; l++) {
- for (ll r = 1; r <= h1; r++) {
- for (ll i = 0; i < n; i++) {
- if (h[i] <= r && l % w[i] == 0) {
- dp[l][r] = max(dp[l][r], dp[l][r - h[i]] + l/w[i]);
- }
- if (w[i] <= l && r % h[i] == 0) {
- dp[l][r] = max(dp[l][r], dp[l - w[i]][r] + r/h[i]);
- }
- }
- ll k1 = -inf, k2 = -inf;
- if (l > 0) {
- k1 = pref_mx[l - 1][r];
- }
- if(r>0) {
- k2 = pref_mx[l][r - 1];
- }
- pref_mx[l][r] = max(max(k1, k2), dp[l][r]);
- dp[l][r] = max(dp[l][r], pref_mx[l][r]);
- //cout << l << ' ' << r << ' ' << dp[l][r] << '\n';
- }
- }
- cout << dp[w1][h1] <<'\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement