Submission #44909874

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

// clang-format off
/* accelration */
// 高速バイナリ生成
//#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// cin cout の結びつけ解除, stdioと同期しない(入出力非同期化)
// cとstdの入出力を混在させるとバグるので注意
struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;

/* alias */
// type
using ull = unsigned long long;
using ll = long long;
using ld = long double;
// pair
using pii = pair<int, int>;
// vector
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using vpii = vector<pii>;
// unordered set
using usi = unordered_set<int>;
using usll = unordered_set<ll>;
using uss = unordered_set<string>;

/* define short */
#define pb push_back
#define mp make_pair
#define um unordered_map
#define all(obj) (obj).begin(), (obj).end()
#define YESNO(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(bool) if(bool){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

/* REP macro */
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) reps(i, 1, n + 1)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define rrepd(i,n) for(ll i=n;i>=1;i--)
#define fore(i,a) for(auto &i:a)

/* func */
inline int in_int() {int x; cin >> x; return x;}
inline ll in_ll() {ll x; cin >> x; return x;}
inline double in_double() {{double x; cin >> x; return x;}}
inline string in_str() {string x; cin >> x; return x;}
inline vs in_vs(ll n) {vs x(n); rep(i,n) cin >> x[i]; return x;}
inline vll in_vll(int n) { vll x(n); rep(i,n) cin >> x[i]; return x;}
inline int ctoi(char c) {return c - '0';}
inline ll sum(vll a) { return accumulate(all(a),0LL);}

// vector_finder: (arg)elementを vectorの先頭から(arg)search_lengthまで先頭から検索し、boolを返す
// (arg)search_length: 走査するベクトル長の上限(先頭から何要素目までを検索対象とするか、1始まりで)
template <typename T> inline bool vector_finder(std::vector<T> vec, T element, unsigned int search_length) {
    auto itr = std::find(vec.begin(), vec.end(), element);
    size_t index = std::distance( vec.begin(), itr );
    if (index == vec.size() || index >= search_length) {return false;} else {return true;}
}
template <typename T> inline void print(const vector<T>& v, string s = " ")
{rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
template <typename T, typename S> inline void print(const pair<T, S>& p)
{cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << "\n";}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v)
{for (auto&& p : v) print(p);}
template <typename T, typename S> inline void print(const map<T, S>& m)
{for (auto&& p : m) print(p);}
// 第一引数と第二引数を比較し、第一引数(a)をより大きい/小さい値に上書き
template <typename T> inline bool chmin(T& a, const T& b) {bool compare = a > b; if (a > b) a = b; return compare;}
template <typename T> inline bool chmax(T& a, const T& b) {bool compare = a < b; if (a < b) a = b; return compare;}
// gcd lcm
// C++17からは標準実装
// template <typename T> T gcd(T a, T b) {if (b == 0)return a; else return gcd(b, a % b);}
// template <typename T> inline T lcm(T a, T b) {return (a * b) / gcd(a, b);}
// clang-format on

template <typename T> inline map<T,ull> counter(const vector<T>& x) {
    map<T,ull> m;
    fore(xi,x) {
        if(m.find(xi)==m.end()){
            m.insert(make_pair(xi,1));
        }
        else{
            m[xi]+=1;
        }
    }
    return m;
}
inline map<char,ull> counter(const string& x) {
    map<char,ull> m;
    fore(xi,x) {
        if(m.find(xi)==m.end()){
            m.insert(make_pair(xi,1));
        }
        else{
            m[xi]+=1;
        }
    }
    return m;
}

// Sieve of Eratosthenes
class sieve {
    int n;
    vi val;
    
    void init() {
        rep(i, n + 1) val[i] = i;
        for (int i = 2; i * i <= n; i++) {
            if (val[i] != i) continue;
            for (int j = i * 2; j <= n; j += i) {
                if (val[j] == j) val[j] = i;
            }
        }
    }

    public:
        sieve(int n) : n(n), val(n + 1) {
            init();
        }
        
        map<int, int> factorlist(int x) {
            if (n < 2) return {};
            map<int, int> ret;
            int now = x;
            while (now > 1) {
                ret[val[now]]++;
                now /= val[now];
            }
            return ret;
        }
        
        vi unique_factor(int x) {
            map<int, int> m = factorlist(x);
            vi ret;
            for (auto p : m) ret.pb(p.first);
            return ret;
        };
        
        bool isPrime(int x) {
            return x >= 2 and val[x] == x;
        }
        
        int count_divisor(int x) {
            int ret = 1;
            map<int, int> fl = factorlist(x);
            for (auto p : fl) ret *= p.second + 1;
            return ret;
        };
};

inline vector<char> str2charvec(string s) { vector<char> r(s.begin(),s.end()); return r;}

template <typename T> inline vector<pair<T,ll>> runlength(vector<T> x) {
    vector<pair<T,ll>> r;
    ll cnt = 1;
    ll n = x.size();
    rep(i,n-1){
        if(x[i]==x[i+1]){cnt++;}
        else{ r.push_back(make_pair(x[i],cnt));cnt=1;}
        if(i==n-2){
            r.push_back(make_pair(x[n-1],cnt));
        }
    }
    return r;
}

struct ModComb{
    vll fac;
    vll finv;
    ll n = 0;
    ll p = 0;

    ModComb(ll n, ll p): n(n), p(p) {
        fac.resize(n+1);
        finv.resize(n+1);
        vll inv(n+1);

        fac[0] = 1;
        fac[1] = 1;
        finv[0] = 1;
        finv[1] = 1;
        inv[1] = 1;

        for (int i = 2; i < n+1; i++)
        {
            fac[i] = (fac[i-1] * i ) % p;
            inv[i] = (p - ( (p/i) * inv[p%i]) %p ) %p;
            finv[i] = (finv[i-1] * inv[i]) %p;
        }
    }

    ll C(ll n, ll k) {
        if (k<0 || n<k) return 0;
        return ((fac[n] * finv[n-k]) % p * finv[k]) % p;
    }

    ll P(ll n, ll k){
        if (k<0 || n<k) return 0;
        return (fac[n] * finv[k]) % p;
    }

    //n個をk箇所に振り分ける(0もあり)
    ll H(ll n, ll k) {
        if(n==0 && k==0) return 1;
        if (k <= 0 || n < 0) return 0;
        return C(n+k-1, n);
    }
};

#ifdef LOCAL
#include <debug_print/debug_print.hpp>
#  define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#  define dbg(...) cerr << "\033[33m(line:" << __LINE__ << ") "; debug(__VA_ARGS__);
#else
#  define dbg(...) (static_cast<void>(0))
#endif


using mint = atcoder::modint1000000007;

vs rot(vs t){
    ll n = t.size();
    vs res(n,string(n,'x'));
    rep(i,n) rep(j,n){
        res[j][n-i-1] = t[i][j];
    }
    return res;
}

int main(){
    ll n = in_ll();
    ll x = in_ll();
    ll y = in_ll();
    vll a(n);
    vll b(n);

    rep(i,n){
        cin >> a[i] >> b[i];
    }

    vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(x+1, vector<ll>(y+1,numeric_limits<ll>::max())));
    dp[0][0][0] = 0;

    rep(i,n) rep(j,x+1) rep(k,y+1) if(dp[i][j][k] != numeric_limits<ll>::max()) {
        chmin(dp[i+1][j][k],dp[i][j][k]);
        chmin(dp[i+1][min(x,j+a[i])][min(y,k+b[i])], dp[i][j][k]+1);
    }

    dbg(dp[n]);

    print(dp[n][x][y] != numeric_limits<ll>::max() ? dp[n][x][y] : -1);

    return 0;
}

Submission Info

Judge Result