Submission #757075

#	Time	Username	Problem	Language	Result	Execution time	Memory
757075		1bin	Jelly Flavours (IOI20_jelly)	C++14	35 / 100	2061 ms	468 KiB

jelly

#include <bits/stdc++.h>
#include "jelly.h"

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e6 + 5;
vector<tuple<int, int, int>> A, B;
int dp[10005], chk[2003];

int find_maximum_unique(int Amx, int Bmx, vector<int> a, vector<int> b) {
	int n = a.size(), ans = 0, sumA = 0, sum = 0;
    for(int i = 0; i < n; i++){
        A.emplace_back(a[i], b[i], i);
        B.emplace_back(b[i], a[i], i);
    }	
    sort(all(A));
    sort(all(B));
    
    for(int i = 0; i <= n; i++){
        if(i){
            auto&[x, _, ia] = A[i - 1];
            sum += x; sumA = sum;
            chk[ia] = 1;   
        }
        memset(dp, 0, sizeof(dp));
        int sumB = 0, cnt = 0;
        for(int j = 0; j <= n; j++){
            if(j){
                auto&[y, _, ib] = B[j - 1];
                if(chk[ib]){
                    sumA -= a[ib];
                    for(int i = Amx; i >= a[ib]; i--) dp[i] = min(dp[i] + y, dp[i - a[ib]]);
                    for(int i = a[ib] - 1; i >= 0; i--) dp[i] += y;
                    cnt++;
                }
                else sumB += y;    
            }
            
            if(sumA <= Amx && sumB <= Bmx && dp[Amx - sumA] <= Bmx - sumB) ans = max(ans, i + j - cnt);
        }
    }
	return ans;
}
/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, Amx, Bmx;
    cin >> n >> Amx >> Bmx;
    vector<int> a(n), b(n);
    for(auto&x : a) cin >> x;
    for(auto&x : b) cin >> x;
    cout << find_maximum_unique(Amx, Bmx, a, b);
    return 0;
}
*/

/*
3
2 3
2 1 4
2 3 2

5
6 12
5 1 5 6 3
3 5 4 6 7
*/

Compilation message (stderr)

jelly.cpp: In function 'int find_maximum_unique(int, int, std::vector<int>, std::vector<int>)':
jelly.cpp:23:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |             auto&[x, _, ia] = A[i - 1];
      |                  ^
jelly.cpp:31:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |                 auto&[y, _, ib] = B[j - 1];
      |                      ^

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