Submission #441486

#	Time	Username	Problem	Language	Result	Execution time	Memory
441486		vulpes2	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	49 ms	460 KiB

jelly

//#include <atcoder/maxflow.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 

#include <iostream>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iterator>
#include <random>
#include <chrono>
#include <complex>
#include <bitset>
#include <fstream>
 
 
#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

 
//using namespace __gnu_pbds;
//using namespace atcoder;
using namespace std;

const ll modd = (1000LL * 1000LL * 1000LL + 7LL);
//const ll modd = 998244353;


int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
    vector<pair<int,int>> aa, bb;
    forr(i,0,a.size()) {
        aa.push_back(make_pair(a[i],i));
    }
    forr(i,0,b.size()) {
        bb.push_back(make_pair(b[i],i));
    }
    sort(aa.begin(), aa.end());
    sort(bb.begin(), bb.end());
    vector<int> min_cost(10001, modd);
    min_cost[0] = 0;

    int ans = 0;
    int xx = 0;
    int cost = 0;
    int ct = 0;
        forr(j,0,bb.size()) {
            if (cost+bb[j].first<=y) {
                cost += bb[j].first;
                ++ct;
                ans = max(ans, ct);
            } else {
                break;
            }
        }
    forr(i,0,aa.size()) {
        int cy;
        forr(j,0,bb.size()) {
            if (bb[j].second==aa[i].second) { bb[j].second = -1; cy = bb[j].first; }
        }
        int cx = aa[i].first;
        for(int c = 10000; c >= cx; --c) {
            min_cost[c] = min(min_cost[c], min_cost[c-cx]+cy);
        }
        xx += cx;
        int cost = 0;
        if (xx>x) {
            cost = modd;
            for(int c = xx-x; c <= 10000; ++c) {
                cost = min(cost, min_cost[c]);
            }
        }
        if (cost > y) { break; }
        ans = max(ans, i+1);
        int ct = 0;
        forr(j,0,bb.size()) {
            if (bb[j].second == -1) { continue; }
            if (cost+bb[j].first<=y) {
                cost += bb[j].first;
                ++ct;
                ans = max(ans, i+1+ct);
            } else {
                break;
            }
        }
    }

    return ans;
}

Compilation message (stderr)

jelly.cpp: In function 'int find_maximum_unique(int, int, std::vector<int>, std::vector<int>)':
jelly.cpp:29:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
jelly.cpp:49:5: note: in expansion of macro 'forr'
   49 |     forr(i,0,a.size()) {
      |     ^~~~
jelly.cpp:29:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
jelly.cpp:52:5: note: in expansion of macro 'forr'
   52 |     forr(i,0,b.size()) {
      |     ^~~~
jelly.cpp:29:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
jelly.cpp:64:9: note: in expansion of macro 'forr'
   64 |         forr(j,0,bb.size()) {
      |         ^~~~
jelly.cpp:29:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
jelly.cpp:73:5: note: in expansion of macro 'forr'
   73 |     forr(i,0,aa.size()) {
      |     ^~~~
jelly.cpp:29:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
jelly.cpp:75:9: note: in expansion of macro 'forr'
   75 |         forr(j,0,bb.size()) {
      |         ^~~~
jelly.cpp:29:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
jelly.cpp:93:9: note: in expansion of macro 'forr'
   93 |         forr(j,0,bb.size()) {
      |         ^~~~
jelly.cpp:80:58: warning: 'cy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |             min_cost[c] = min(min_cost[c], min_cost[c-cx]+cy);

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