oj.uz

Submission #318657

# Submission time Handle Problem Language Result Execution time Memory
318657 2020-11-02T19:59:10 Z SnowFlake7 Jelly Flavours (IOI20_jelly) C++14
0 / 100
 30 ms 18796 KB 
#include "jelly.h"
#include <bits/stdc++.h>
#define NMAX 2005
#define INF 2000000000

using namespace std;

struct jelly {
	int a, b;
}v[NMAX];
int dp[NMAX][10005],cost[NMAX];

bool cmp1 (jelly a, jelly b){
	return a.a < b.a;
}
bool cmp2 (jelly a, jelly b){
	return a.b < b.b;
}
int find_maximum_unique (int x, int y, vector<int> a, vector<int> b) {
	int ind,ans = 0,rest,n = a.size();
	for (int i = 1;i <= n;i++){
		v[i] = {a[i - 1], b[i - 1]};
	}
	sort(v + 1, v + n + 1, cmp1);
	for (int i = 0;i <= n;i++){
		for(int j = 0;j <= y;j++)
			dp[i][j] = INF;
	}
	dp[0][0] = 0;
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j <= y;j++) {
            if (dp[i - 1][j] == INF)
				continue;
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + v[i].a);
			if (j + v[i].b <= y)
				dp[i][j + v[i].b] = min(dp[i][j + v[i].b], dp[i - 1][j]);
		}
	}
	cost[0] = 0;
	for (int i = 1;i <= n;i++) {
		cost[i] = INF;
		for(int j = 0;j <= y;j++) {
			if(dp[i][j] <= x) {
				cost[i] = j;
				break;
			}
		}
	}
	for (int i = n;i >= 0;i--) {
		if (cost[i] == INF)
			continue;
		rest = y - cost[i];
		if (i < n)
			sort(v + i + 1, v + n + 1, cmp2);
		ind = i + 1;
		while (ind <= n && rest >= 0) {
			rest -= v[ind].b;
			ind++;
		}
		if (ind == n + 1 && rest >=0)
			ans = n;
		else
			ans = max(ans, rest - 2);
	}
	return ans;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 32.0

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