oj.uz

Submission #673214

# Submission time Handle Problem Language Result Execution time Memory
673214 2022-12-19T23:58:09 Z Hacv16 Jelly Flavours (IOI20_jelly) C++17
0 / 100
 2000 ms 94416 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[MAXN][MAXM];
int n, a[MAXN], b[MAXN];

int find_maximum_unique(int x, int y, vector<int> _a, vector<int> _b) {
  n = _a.size();
  
  if(x > y){ swap(x, y); swap(_a, _b); }
  
  for(int i = 1; i <= n; i++) {
    a[i] = _a[i - 1];
    b[i] = _b[i - 1];    
  }
  
  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);
			}
	} 

  int i = n, j = x;

  while(i != 0){
      if(dp[i][j] == dp[i - 1][j]) i--;
      else if(dp[i][j] == dp[i - 1][j - a[i]] + 1){
          i--, j -= a[i], b[i] = INF; 
      }
  }

  for(int i = 1; i <= n; i++){
			for(int j = 0; j <= y; j++){
				dp2[i][j] = dp2[i - 1][j];
 
				 if(j >= b[i]) 
					   dp2[i][j] = max(dp2[i][j], dp2[i - 1][j - b[i]] + 1);
			}
	}

  return (dp[n][x] + dp2[n][y]);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 29140 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 54 ms 94416 KB Output is correct
2 Execution timed out 2082 ms 78012 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 93260 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 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '8', found: '7'
4 Halted 0 ms 0 KB -