Submission #45001360

---

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 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
// https://youtu.be/UTVg7wzMWQc?t=2774
struct Sieve {
    int n;
    vector<int> f, primes;
    Sieve(int n=1):n(n), f(n+1) {
        f[0] = f[1] = -1;
        for (ll i = 2; i <= n; ++i) {
            if (f[i]) continue;
            primes.push_back(i);
            f[i] = i;
            for (ll j = i*i; j <= n; j += i) {
                if (!f[j]) f[j] = i;
            }
        }
    }
    bool isPrime(int x) { return f[x] == x;}
    ll minfactor(ll x) { return f[x];}
    vector<int> factorList(int x) {
        vector<int> res;
        while (x != 1) {
            res.push_back(f[x]);
            x /= f[x];
        }
        return res;
    }
    vector<pii> factor(int x) {
        vector<int> fl = factorList(x);
        if (fl.size() == 0) return {};
        vector<pii> res(1, pii(fl[0], 0));
        for (int p : fl) {
            if (res.back().first == p) {
                res.back().second++;
            } else {
                res.emplace_back(p, 1);
            }
        }
        return res;
    }
    vector<pair<ll,int>> factor(ll x) {
        vector<pair<ll,int>> res;
        for (int p : primes) {
            int y = 0;
            while (x%p == 0) x /= p, ++y;
            if (y != 0) res.emplace_back(p,y);
        }
        if (x != 1) res.emplace_back(x,1);
        return res;
    }
};

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);
    }
};
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;
};

#define INF (ll)1e18

#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

int main() {
    ll n = in_ll();
    ll tz=0;
    ll az=0;

    vpii a;

    rep(i,n){
        ll x = in_ll();
        ll y = in_ll();
        ll z = in_ll();
        if(x>y) tz+=z;
        else{
            az+=z;
            a.pb({(y-x+1)/2,z});
        }
    }

    if(tz>az) {print(0); return 0;}

    ll mz = (az-tz+1)/2;

    vvll dp(a.size()+1, vll(mz+2,INF));
    dp[0][0] = 0;
    rep(i, a.size()){
        rep(j,mz+1){
            if(dp[i][j] != INF){
                chmin(dp[i+1][j],dp[i][j]);
                chmin(dp[i+1][min(mz,j+a[i].second)], dp[i][j]+a[i].first);
            }
        }
    }

    print(dp[a.size()][mz]);

    return 0;
}

Submission Info

Judge Result