oj.uz

Submission #725510

# Submission time Handle Problem Language Result Execution time Memory
725510 2023-04-17T14:38:01 Z vjudge1 Schools (IZhO13_school) C++17
25 / 100
 6 ms 6692 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);
int memo[101][101][101]; 

int dp(int i, int n, int M, int S, int m, int s) {
  if (S == s && m == M) return 0;
  if (i > n) return -inf;

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

  int ans = dp(i + 1, n, M, S, m, s);
  if (M > m) ans = max(ans, dp(i + 1, n, M, S, m + 1, s) + v[i].F);
  if (S > s) ans = max(ans, dp(i + 1, n, M, S, m, s + 1) + v[i].S);

  return memo[i][m][s] = ans;
}

int32_t main () {
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr);

  for (int i = 0; i <= 100; i ++) {
    for (int j = 0; j <= 100; j ++) {
      for (int k = 0; k <= 100; k ++) {
        memo[i][j][k] = -1;
      }
    }
  }

  int n, m, s; cin >> n >> m >> s;
  if (n > 100) return 0;

  for (int i = 1; i <= n; i ++) {
    cin >> v[i].F >> v[i].S;
  }

  cout << dp(0, n, m, s, 0, 0);

  return 0;
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 6 ms 6612 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Incorrect 4 ms 6612 KB Output isn't correct
7 Incorrect 4 ms 6612 KB Output isn't correct
8 Incorrect 4 ms 6644 KB Output isn't correct
9 Incorrect 3 ms 6612 KB Output isn't correct
10 Incorrect 3 ms 6612 KB Output isn't correct
11 Incorrect 3 ms 6656 KB Output isn't correct
12 Incorrect 3 ms 6612 KB Output isn't correct
13 Incorrect 3 ms 6612 KB Output isn't correct
14 Incorrect 3 ms 6612 KB Output isn't correct
15 Incorrect 3 ms 6612 KB Output isn't correct
16 Incorrect 3 ms 6692 KB Output isn't correct
17 Incorrect 3 ms 6612 KB Output isn't correct
18 Incorrect 3 ms 6612 KB Output isn't correct
19 Incorrect 4 ms 6612 KB Output isn't correct
20 Incorrect 4 ms 6612 KB Output isn't correct