Submission #400917

#	Time	Username	Problem	Language	Result	Execution time	Memory
400917		iulia13	Jelly Flavours (IOI20_jelly)	C++14	35 / 100	179 ms	77472 KiB

jelly

#include <iostream>
#include "jelly.h"
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e3 + 5;
const int V = 1e4 + 5;;
int dp[N][V];
int cost[N];
struct ura{
    int a, b;
};
bool cmp1(ura x, ura y)
{
    return x.a < y.a;
}
bool cmp2(ura x, ura y)
{
    return x.b < y.b;
}
ura v[V];
int find_maximum_unique(int x, int y, vector <int> A, vector <int> B)
{
    int i, j, ans = 0, n;
    n = A.size();
    for (i = 1; i <= n; i++)
        v[i] = {A[i - 1], B[i - 1]};
    sort(v + 1, v + n + 1, cmp2);
    for (i = 0; i <= n; i++)
        for (j = 0; j <= x; j++)
            dp[i][j] = 2e9;
    dp[0][0] = 0;
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j <= x; j++)
        {
            if (dp[i - 1][j] == 2e9)
                continue;
            dp[i][j + v[i].a] = min(dp[i][j], dp[i - 1][j]);
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + v[i].b);
        }
    }
    for (i = 0; i <= n; i++)
    {
        cost[i] = 2e9;
        for (j = 0; j <= x && cost[i] == 2e9; j++)
            if (dp[i][j] <= y)
                cost[i] = j;
    }
    for (i = n; 0 <= i; i--)
    {
        if (cost[i] == 2e9)
            continue;
        int need = x - cost[i];
        sort(v + i + 1, v + n + 1, cmp1);
        j = i + 1;
        while (j <= n && need >= v[j].a)
        {
            need -= v[j].a;
            j++;
        }
        ans = max(ans, j - 1);
    }
    return ans;
 
}/*
vector <int> A, B;
int main()
{
    int x, y, n, m;
    cin >> n >> x >> y;
    m = n;
    A.resize(n);
    B.resize(m);
    for (int i = 0; i < n; i++)
        cin >> A[i] >> B[i];
    cout << find_maximum_unique(x, y, A, B);
    return 0;
}*/

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 0 / 9
• Subtask 4: 0 / 10
• Subtask 5: 0 / 14
• Subtask 6: 0 / 32