Submission #73566344

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;


template<typename T>
void input(int n, vector<T>&v){
    v.assign(n + 1, {});
    for(int i=1;i<=n;++i)cin>>v[i];
    return;
}

template<typename T>
istream & operator >> (istream & is, vector<T>&v){
    for(auto & i : v)is>>i;
    return is;
}

ostream & operator << (ostream & os, __int128_t i){
    if(0 == i) return os << 0;
    if(i < 0){
        os << '-';
        i = -i;
    }
    vector<int> vec;
    while(i){
        vec.emplace_back(i % 10);
        i /= 10;
    }
    for(auto it=vec.rbegin(),et=vec.rend();it!=et;++it) os << *it;
    return os;
}

template<typename T>
ostream & operator << (ostream & os, const vector<T> & v){
    os << *v.begin();
    for(auto it=++v.begin(),et=v.end();it!=et;++it){
        os << " " << *it;
    }
    return os;
}

template<typename T>
string toString(const vector<T> & v){
    stringstream ss;
    ss << v;
    return ss.str();
}

using llt = long long;
// using llt = __int128_t;
using vi = vector<int>;
using vll = vector<llt>;
using arr = array<int, 2>;
using pii = pair<int, int>;


int N;
int M;
vi A;
vll B;
vector<vll> D;
vector<vll> E;

void chkmax(llt & d, llt a){
    if(d < a) d = a;
}

void work(){
    cin >> N >> M;
    A.assign(N + 1, 0);
    B.assign(N + 1, 0);
    for(int i=1;i<=N;++i){
        cin >> A[i] >> B[i];
    }
    
    D.assign(N + 1, vll(M + 1, 0));
    for(int i=1;i<=N;++i){
        const auto & pre = D[i - 1];
        auto & d = D[i];
        d.assign(pre.begin(), pre.end());
        for(int v=A[i];v<=M;++v){
            chkmax(d[v],pre[v - A[i]] + B[i]);
        }
    }

    E.assign(N + 2, vll(M + 1, 0));
    for(int i=N;i>=1;--i){
        const auto & pre = E[i + 1];
        auto & d = E[i];
        d.assign(pre.begin(), pre.end());
        for(int v=A[i];v<=M;++v){
            chkmax(d[v],pre[v - A[i]] + B[i]);
        }
    }

    assert(D[N][M] == E[1][M]);

    auto target = D[N][M];
    vi ans(N + 1, 0);
    for(int i=1;i<=N;++i){
        const auto & pre = D[i - 1];
        const auto & nxt = E[i + 1];
        for(int v=0;v<=M-A[i];++v){
            auto u = M - A[i] - v;
            if(pre[u] + nxt[v] + B[i] == target){
                ans[i] = 1;
            }else if(pre[v] + nxt[u] + B[i] == target){
                ans[i] = 1;
            }
        }
    }

    for(int i=1;i<=N;++i){
        if(ans[i]) cout << "Yes\n";
        else cout << "No\n";
    }
    return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase;
    while(nofkase--) work();
    return 0;
}

Submission Info

Judge Result