oj.uz

Submission #725540

# Submission time Handle Problem Language Result Execution time Memory
725540 2023-04-17T15:14:01 Z vjudge1 Schools (IZhO13_school) C++17
20 / 100
 364 ms 262148 KB 
#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<ll, ll>> v(MAXN);
vector<vector<ll>> memo(5001, vector<ll> (5001, -1));

ll dp(ll i, ll M, ll S, ll m) {
  if (i == M + S) return 0;

  if (memo[i][m] != -1) return memo[i][m];

  ll 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);

  ll n, m, s; cin >> n >> m >> s;

  for (ll i = 1; i <= n; i ++) {
    cin >> v[i].F >> v[i].S;
  }
  sort(v.rbegin(), v.rend());
  ll ans = dp(0, m, s, 0);
  for (ll i = 0; i < n; i ++) 
    swap(v[i].F, v[i].S);

  for (ll i = 0; i <= 5000; 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;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 200916 KB Output is correct
2 Correct 113 ms 200936 KB Output is correct
3 Correct 112 ms 200876 KB Output is correct
4 Incorrect 111 ms 200924 KB Output isn't correct
5 Incorrect 113 ms 200960 KB Output isn't correct
6 Incorrect 113 ms 200960 KB Output isn't correct
7 Incorrect 130 ms 200952 KB Output isn't correct
8 Correct 130 ms 201204 KB Output is correct
9 Incorrect 192 ms 201224 KB Output isn't correct
10 Incorrect 138 ms 201164 KB Output isn't correct
11 Incorrect 182 ms 201108 KB Output isn't correct
12 Incorrect 128 ms 201072 KB Output isn't correct
13 Runtime error 318 ms 262148 KB Execution killed with signal 11
14 Runtime error 304 ms 262144 KB Execution killed with signal 11
15 Runtime error 317 ms 262144 KB Execution killed with signal 11
16 Runtime error 327 ms 262144 KB Execution killed with signal 11
17 Runtime error 336 ms 262144 KB Execution killed with signal 11
18 Runtime error 345 ms 262144 KB Execution killed with signal 11
19 Runtime error 344 ms 262144 KB Execution killed with signal 11
20 Runtime error 364 ms 262144 KB Execution killed with signal 11