# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
725538 | vjudge1 | Schools (IZhO13_school) | C++17 | 145 ms | 262144 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ld long double
#define ll long long
#define S second
#define F first
using namespace __gnu_pbds;
using namespace std;
typedef tree<long long, null_type, less_equal<long long>,
rb_tree_tag, tree_order_statistics_node_update> Tree;
const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MAXN = 300010;
const ll MOD = 1e9 + 7;
const ld PI = acos(-1);
const ll NROOT = 320;
ll binpow(ll a, ll b) {
ll res = 1;
for (;b; b /= 2, a *= a, a %= MOD)
if (b & 1) res *= a, res %= MOD;
return res % MOD;
}
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll invmod(ll a) {return binpow(a, MOD - 2);}
vector<pair<int, int>> v(MAXN);
vector<vector<int>> memo(10000, vector<int> (10000, -1));
int dp(int i, int M, int S, int m) {
if (i == M + S) return 0;
if (memo[i][m] != -1) return memo[i][m];
int ans = 0;
if (M > m) ans = max(ans, dp(i + 1, M, S, m + 1) + v[i].F);
if (S > i - m) ans = max(ans, dp(i + 1, M, S, m) + v[i].S);
return memo[i][m] = ans;
}
int32_t main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s; cin >> n >> m >> s;
for (int i = 1; i <= n; i ++) {
cin >> v[i].F >> v[i].S;
}
sort(v.rbegin(), v.rend());
int ans = dp(0, m, s, 0);
for (int i = 0; i < n; i ++)
swap(v[i].F, v[i].S);
for (int i = 0; i <= 1000; i ++) {
for (auto &x : memo[i])
x = -1;
}
sort(v.rbegin(), v.rend());
ans = max(ans, dp(0, s, m, 0));
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |