oj.uz

Submission #725539

# Submission time Handle Problem Language Result Execution time Memory
725539 2023-04-17T15:11:51 Z vjudge1 Schools (IZhO13_school) C++17
20 / 100
 212 ms 204856 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<int, int>> v(MAXN);
vector<vector<int>> memo(5000, vector<int> (5000, -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;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 100700 KB Output is correct
2 Correct 55 ms 100640 KB Output is correct
3 Correct 60 ms 100624 KB Output is correct
4 Incorrect 56 ms 100688 KB Output isn't correct
5 Incorrect 58 ms 100684 KB Output isn't correct
6 Incorrect 56 ms 100620 KB Output isn't correct
7 Incorrect 71 ms 100744 KB Output isn't correct
8 Correct 77 ms 100980 KB Output is correct
9 Incorrect 139 ms 100968 KB Output isn't correct
10 Incorrect 79 ms 100980 KB Output isn't correct
11 Incorrect 133 ms 101084 KB Output isn't correct
12 Incorrect 71 ms 100984 KB Output isn't correct
13 Runtime error 139 ms 204740 KB Execution killed with signal 11
14 Runtime error 144 ms 204700 KB Execution killed with signal 11
15 Runtime error 212 ms 204768 KB Execution killed with signal 11
16 Runtime error 170 ms 204856 KB Execution killed with signal 11
17 Runtime error 178 ms 204748 KB Execution killed with signal 11
18 Runtime error 186 ms 204848 KB Execution killed with signal 11
19 Runtime error 190 ms 204844 KB Execution killed with signal 11
20 Runtime error 195 ms 204772 KB Execution killed with signal 11