Submission #44955256

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<std::vector<T>> &r){
    if(r.size() == 0){
        out << "||";
        return out;
    }
    for(const auto&v : r) out << v << endl;
    out << endl;
    return out;
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &r){
    if(r.size() == 0){
        out << "[]";
        return out;
    }
    out << "[";
    for(int i{}; i < (int)r.size() - 1; ++i) out << r[i] << ",";
    out << r.back() << "]";
    return out;
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::set<T> &r){
    if(r.size() == 0){
        out << "{}";
        return out;
    }
    out << "{";
    auto e = r.end(); --e;
    for(auto it = r.begin(); it != e; ++it) out << *it << ",";
    out << *e << "}";
    return out;
}

template <class T, class U>
std::ostream &operator<<(std::ostream &out, const std::map<T, U> &r){
    if(r.size() == 0){
        out << "{}";
        return out;
    }
    out << "{";
    auto e = r.end(); --e;
    for(auto it = r.begin(); it != e; ++it) out << it -> first << ":" << it -> second << ",";
    out << e -> first << ":" << e -> second << "}";
    return out;
}
 
template <class T, class U>
std::ostream &operator<<(std::ostream &out, const std::pair<T, U> &r){
    out << "(" << r.first << "," << r.second << ")";
    return out;
}

void solve(){
    int n;
    cin >> n;
    vector<int> x(n), y(n), z(n);
    int Z = 0, T = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> z[i];
        Z += z[i];
        if(x[i] > y[i]) T += z[i];
    }
    constexpr ll inf = 1e16;
    vector<ll> d(Z+1, inf);
    d[T] = 0;
    for (int i = 0; i < n; i++)
    {
        if(x[i] > y[i]) continue;
        int k = (y[i] - x[i] + 1) / 2;
        for (int j = Z; j >= z[i]; j--)
        {
            chmin(d[j], d[j-z[i]] + k);
        }
    }
    ll ans = inf;
    for (int i = (Z+1)/2; i <= Z; i++)
    {
        chmin(ans, d[i]);
    }
    cout << ans << endl;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

Submission Info

Judge Result