oj.uz

Submission #673228

# Submission time Handle Problem Language Result Execution time Memory
673228 2022-12-20T00:52:25 Z ThegeekKnight16 Jelly Flavours (IOI20_jelly) C++17
0 / 100
 146 ms 78368 KB 
#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e3 + 10;
const int MAXM = 1e4 + 10;
const int INF = 0x3f3f3f3f;

int dp[MAXN][MAXM];
// int dp2[MAXM];
int n, a[MAXN], b[MAXN];
vector<pair<int, int> > buga;

void limpar(int n, int m)
{
    for (int i = 1; i <= n; i++)
      {
        for(int j = 0; j <= m; j++){
          dp[i][j] = 0;
        }
      }
}

int find_maximum_unique(int x, int y, vector<int> _a, vector<int> _b) {
  n = _a.size();
  //if (rand() % 2) {
    // swap(x, y);
    // swap(_a, _b);
  // }

  for (int i = 0; i < n; i++)
    buga.emplace_back(_a[i], _b[i]);

  sort(buga.begin(), buga.end());

  for (int i = 1; i <= n; i++) {
    a[i] = buga[i - 1].first;
    b[i] = buga[i - 1].second;
  }

  for (int i = 1; i <= n; i++) {
    for (int j = x; j >= 0; j--) {
      dp[i][j] = dp[i - 1][j];

      if (j >= a[i])
        dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + 1);
    }
  }

  for(int i = n, j = x; i >= 1; i--)
  {
      if (j >= a[i] && dp[i][j] == dp[i-1][j - a[i]] + 1) {
        j -= a[i]; b[i] = INF;
      }
  }

  int ans = dp[n][x];

  limpar(n, x);

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= y; j++) {
      dp[i][j] = dp[i - 1][j];

      if (j >= b[i])
        dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + 1);
    }
  }

  ans += dp[n][y];

  limpar(n, y);

  for (int i = 1; i <= n; i++) {
    a[i] = buga[i - 1].first;
    b[i] = buga[i - 1].second;
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= y; j++) {
      dp[i][j] = dp[i - 1][j];

      if (j >= b[i])
        dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + 1);
    }
  }

  for(int i = n, j = x; i >= 1; i--)
  {
      if (j >= a[i] && dp[i][j] == dp[i-1][j - b[i]] + 1) {
        j -= b[i]; a[i] = INF;
      }
  }

  int ans2 = dp[n][y];
  limpar(n, y);

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= x; j++) {
      dp[i][j] = dp[i - 1][j];

      if (j >= a[i])
        dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + 1);
    }
  }

  ans2 += dp[n][x];

  return max(ans, ans2);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB 1st lines differ - on the 1st token, expected: '8', found: '9'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB 1st lines differ - on the 1st token, expected: '8', found: '9'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 21204 KB 1st lines differ - on the 1st token, expected: '689', found: '700'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 76168 KB Output is correct
2 Correct 130 ms 78060 KB Output is correct
3 Correct 135 ms 78368 KB Output is correct
4 Incorrect 146 ms 75048 KB 1st lines differ - on the 1st token, expected: '1906', found: '3242'
5 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 77204 KB 1st lines differ - on the 1st token, expected: '154', found: '195'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB 1st lines differ - on the 1st token, expected: '8', found: '9'
2 Halted 0 ms 0 KB -