結果

問題 No.1861 Required Number
ユーザー noya2noya2
提出日時 2022-03-05 10:00:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 112 ms / 2,500 ms
コード長 12,851 bytes
コンパイル時間 4,232 ms
コンパイル使用メモリ 285,900 KB
実行使用メモリ 82,304 KB
最終ジャッジ日時 2024-07-19 09:56:45
合計ジャッジ時間 13,330 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 111 ms
82,304 KB
testcase_04 AC 112 ms
82,176 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 36 ms
29,952 KB
testcase_25 AC 92 ms
71,168 KB
testcase_26 AC 16 ms
14,620 KB
testcase_27 AC 32 ms
27,392 KB
testcase_28 AC 38 ms
31,232 KB
testcase_29 AC 24 ms
19,200 KB
testcase_30 AC 8 ms
6,656 KB
testcase_31 AC 97 ms
72,576 KB
testcase_32 AC 11 ms
8,960 KB
testcase_33 AC 65 ms
50,304 KB
testcase_34 AC 79 ms
59,008 KB
testcase_35 AC 79 ms
59,904 KB
testcase_36 AC 24 ms
20,096 KB
testcase_37 AC 38 ms
29,952 KB
testcase_38 AC 79 ms
60,928 KB
testcase_39 AC 43 ms
34,816 KB
testcase_40 AC 96 ms
72,192 KB
testcase_41 AC 91 ms
68,224 KB
testcase_42 AC 73 ms
55,552 KB
testcase_43 AC 39 ms
30,848 KB
testcase_44 AC 1 ms
5,376 KB
04_evil_1.txt MLE -
04_evil_2.txt MLE -
04_evil_3.txt MLE -
04_evil_4.txt MLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'std::vector<int> Graph::dfs(int)':
main.cpp:148:5: warning: no return statement in function returning non-void [-Wreturn-type]
  148 |     }
      |     ^

ソースコード

diff # 

#include <bits/stdc++.h>
/*
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using bint = mp::cpp_int;
*/
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define repp(i,n,m) for (int i = m; i < int(n); ++i)
#define repb(i,n) for (int i = int(n)-1; i >= 0; --i)
#define fi first
#define se second
#define endl "\n"
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<long double, long double>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
const int INF = 1001001007;
const long long mod1 = 1000000007LL;
const long long mod2 = 998244353LL;
const ll inf = 2e18;
const ld pi = 3.14159265358979323;
const ld eps = 1e-7;
const char _ = ' ';
template<class T>istream &operator>>(istream &is,vector<T> &v){for(auto &e:v)is>>e;return is;}
template<class T>ostream &operator<<(ostream &os,const vector<T> &v){if(v.size()!=0){rep(i,v.size())os<<v[i]<<(i+1==v.size()?"":" ");}return os;}
template<class T>istream &operator>>(istream &is,vector<vector<T>> &v){for(auto &e:v)is>>e;return is;}
template<class T>ostream &operator<<(ostream &os,const vector<vector<T>> &v){if(v.size()!=0){for(auto &e:v)os<<e;}return os;}
template<typename T>bool range(T a,T b,T x){return (a<=x&&x<b);}
template<typename T>bool rrange(T a,T b,T c,T d,T x,T y){return (range(a,c,x)&&range(b,d,y));}
template<typename T>void rev(vector<T> &v){reverse(v.begin(),v.end());}
void revs(string &s) {reverse(s.begin(),s.end());}
template<typename T>void sor(vector<T> &v, int f=0){sort(v.begin(),v.end());if(f!=0) rev(v);}
template<typename T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<typename T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<typename T>void eru(vector<T> &v){sor(v);v.erase(unique(v.begin(),v.end()),v.end());}
template<typename T>T cel(T a,T b){if(a%b==0)return a/b;return a/b +1;}
void o(){cout<<"!?"<<endl;}
template<typename T>void o(T a){cout<<a<<endl;}
template<typename T,typename U>void o2(T a,U b){cout<<a<<_<<b<<endl;}
template<typename T,typename U>void o2(pair<T,U> a){o2(a.first,a.second);}
template<typename T,typename U,typename V>void o3(T a,U b,V c){cout<<a<<_<<b<<_<<c<<endl;}
template<typename T>void mout(T a){cout<<a.val()<<endl;}
void yes(){cout << "Yes" << endl;}
void no (){cout << "No" << endl;}
void yn (bool t){if(t)yes();else no();}
template<typename T>void dame(bool t, T s){if(!t){cout << s << endl;exit(0);}}
void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);}
vector<int> dx = {0,1,0,-1};
vector<int> dy = {1,0,-1,0};
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string num = "0123456789";

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mpow(ll x,ll n,ll m){if(n==0)return 1LL;x%=m;ll a=mpow(x,n/2,m);a=a*a%m;return (n&1)?a*x%m:a;}

ll tentou(vector<ll> ar){
    int n = ar.size();
    set<ll> st;
    rep(i,n) st.insert(ar[i]);
    map<ll,int> mp;
    int ind = 0;
    for (ll x : st){
        mp[x] = ind;
        ind++;
    }
    fenwick_tree<ll> fw(ind);
    ll ans = 0;
    rep(i,n){
        int a = mp[ar[i]];
        ans += i - fw.sum(0,a+1);
        fw.add(a,1);
    }
    return ans;
}

struct edge{
    int from, to, idx;
    long long cost;
    edge(int _from = -1, int _to = -1, long long _cost = 1LL, int _idx = -1) : from(_from), to(_to), cost(_cost), idx(_idx) {}
};

struct vertex{
    vector<edge> adj;
};

struct Graph{
    int n, m;
    vector<vertex> ar;
    void add_edge(int from, int to, long long cost = 1LL){
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        ar[from].adj.emplace_back(edge(from,to,cost));
    }
    void add_dual_edge(int from, int to, long long cost = 1LL){
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        ar[from].adj.emplace_back(edge(from,to,cost));
        ar[to].adj.emplace_back(edge(to,from,cost));
    }
    Graph(int _n) : n(_n) , ar(n) {}
    vector<long long> dijkstra(int s){
        using pli = pair<long long, int>;
        priority_queue<pli, vector<pli>, greater<pli>> pque;
        vector<long long> dist(n,inf);
        dist[s] = 0LL;
        pque.push(pli(0,s));
        while (!pque.empty()){
            pli p = pque.top(); pque.pop();
            if (dist[p.second] < p.first) continue;
            for (edge x : ar[p.second].adj){
                if (dist[x.to] > p.first + x.cost){
                    dist[x.to] = p.first + x.cost;
                    pque.push(pli(dist[x.to],x.to));
                }
            }
        }
        return dist;
    }
    vector<long long> bfs01(int s){
        deque<int> que;
        vector<long long> dist(n,inf);
        dist[s] = 0LL;
        que.push_front(s);
        while (!que.empty()){
            int p = que.front(); que.pop_front();
            for (edge x : ar[p].adj){
                if (dist[x.to] > dist[p] + x.cost){
                    dist[x.to] = dist[p] + x.cost;
                    if (x.cost == 0LL) que.push_front(x.to);
                    else que.push_back(x.to);
                }
            }
        }
        return dist;
    }
    vector<int> dfs(int s){
        vector<int> ans;
        vector<int> vis(n,0);
        _dfs(s,ans,vis);
    }
    private:
    void _dfs(int s, vector<int> &ans, vector<int> &vis){
        vis[s]++;
        for (edge x : ar[s].adj){
            if (vis[x.to] == 0){
                _dfs(x.to,ans,vis);
            }
        }
        ans.emplace_back(s);
    }
};

struct Tree{
    Tree(int _n, int _root = 0) : n(_n), root(_root) {
        assert(0 <= root && root < n);
        initialize();
    }
    void add_edge(int from, int to, long long cost = 1LL, int _idx = -1){
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        if (_idx == -1) _idx = m, m++;
        assert(0 <= _idx && _idx < n-1);
        assert(edge_idx_cnt[_idx] == 0);
        edge_idx_cnt[_idx]++;
        vs[from].adj.emplace_back(edge(from,to,cost,_idx));
        es[_idx] = edge(from,to,cost,_idx);
    }
    void add_dual_edge(int from, int to, long long cost = 1LL, int _idx = -1){
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        if (_idx == -1) _idx = m, m++;
        assert(0 <= _idx && _idx < n-1);
        assert(edge_idx_cnt[_idx] == 0);
        edge_idx_cnt[_idx]++;
        vs[from].adj.emplace_back(edge(from,to,cost,_idx));
        vs[to].adj.emplace_back(edge(to,from,cost,_idx));
        es[_idx] = edge(from,to,cost,_idx);
    }
    int size(){return n;}
    int parent(int v){
        assert(0 <= v && v < n);
        if (is_done_par_rdist_init == false) par_rdist_init();
        return par[v];
    }
    int depth(int v){
        assert(0 <= v && v < n);
        if (dep[v] != -1) return dep[v];
        if (v == root) return dep[v] = 0;
        return dep[v] = depth(parent(v)) + 1;
    }
    int subtree_size(int v){
        assert(0 <= v && v < n);
        if (sub[v] != 0) return sub[v];
        sub[v] = 1;
        for (edge x : vs[v].adj){
            if (x.to != parent(v)) sub[v] += subtree_size(x.to);
        }
        return sub[v];
    }
    int lca(int u, int v){
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        if (is_done_lca_init == false) lca_init();
        if (depth(u) > depth(v)) swap(u,v);
        for (int i = 0; i < 30; i++) if ((depth(v) - depth(u)) >> i & 1) v = par2[i][v];
        if (u == v) return u;
        for (int k = 29; k >= 0; k--){
            if (par2[k][u] != par2[k][v]) {
                u = par2[k][u];
                v = par2[k][v];
            }
        }
        return par2[0][u];
    }
    long long dist(int u, int v){
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        if (is_done_par_rdist_init == false) par_rdist_init();
        return rdist[u] + rdist[v] - rdist[lca(u,v)] * 2LL;
    }
    vector<int> path(int f, int t){
        assert(0 <= f && f < n);
        assert(0 <= t && t < n);
        int v = lca(f,t);
        vector<int> fp = {f};
        vector<int> tp = {t};
        int fn = f, tn = t;
        while (fn != v){
            fn = parent(fn);
            fp.emplace_back(fn);
        }
        while (tn != v){
            tn = parent(tn);
            tp.emplace_back(tn);
        }
        for (int i = int(tp.size()) - 2; i >= 0; i--){
            fp.emplace_back(tp[i]);
        }
        return fp;
    }
    vector<long long> alldists(int v){
        assert(0 <= v && v < n);
        if (v == 0) return rdist;
        vector<long long> dists(n,1e18);
        vector<int> vis(n,0);
        dists[v] = 0LL;
        queue<int> que;
        que.push(v);
        while (!que.empty()){
            int p = que.front(); que.pop();
            vis[p]++;
            for (edge x : vs[p].adj){
                if (vis[x.to] == 0){
                    dists[x.to] = dists[p] + x.cost;
                    que.push(x.to);
                }
            }
        }
        return dists;
    }
    vector<int> dfs(int v){
        assert(0 <= v && v < n);
        vector<int> ans;
        vector<int> vis(n,0);
        _dfs(v,vis,ans);
        return ans;
    }
    edge to_parent(int v){
        assert(0 <= v && v < n && v != root);
        if (is_done_par_rdist_init == false) par_rdist_init();
        return es[epar[v]];
    }
    vector<vertex> vs;
    private:
    int n;
    int m;
    int root;
    int idx_vhfs;
    bool is_done_lca_init;
    bool is_done_par_rdist_init;
    vector<edge> es;
    vector<int> edge_idx_cnt;
    vector<int> par;
    vector<int> epar;
    vector<int> dep;
    vector<int> sub;
    vector<int> top;
    vector<long long> rdist;
    vector<vector<int>> par2;
    void initialize(){
        m = 0;
        is_done_lca_init = false;
        is_done_par_rdist_init = false;
        vs.resize(n);
        es.resize(n-1);
        edge_idx_cnt.resize(n-1,0);
        dep.resize(n,-1);
        sub.resize(n,0);
    }
    void lca_init(){
        par2.resize(30,vector<int>(n,-1));
        for (int i = 0; i < n; i++) par2[0][i] = parent(i);
        for (int i = 0; i < 29 ; i++) {
            for (int j = 0; j < n; j++) {
                if (par2[i][j] < 0) par2[i+1][j] = -1;
                else par2[i+1][j] = par2[i][par2[i][j]];
            }
        }
        is_done_lca_init = true;
    }
    void par_rdist_init(){
        par.resize(n,-2);
        epar.resize(n);
        rdist.resize(n,-1);
        par[root] = -1;
        rdist[root] = 0;
        queue<int> que;
        que.push(root);
        while (!que.empty()){
            int p = que.front(); que.pop();
            for (edge x : vs[p].adj){
                if (par[x.to] == -2){
                    par[x.to] = p;
                    epar[x.to] = x.idx;
                    rdist[x.to] = rdist[p] + x.cost;
                    que.push(x.to);
                }
            }
        }
        is_done_par_rdist_init = true;
    }
    void _dfs(int v, vector<int> &vis, vector<int> &ans){
        vis[v]++;
        for (edge x : vs[v].adj){
            if (vis[x.to] == 0) _dfs(x.to,vis,ans);
        }
        ans.emplace_back(v);
    }
};


template<typename T>
struct doubling{
    vector<T> vec;
    doubling (vector<T> _vec) : vec(_vec) {}
    map<T,ll> mp;
    ll length_of_loop = -1;
    ll top_of_loop = -1;
    void init(){
        ll ind = 0;
        for (T x : vec){
            if (mp.find(x) == mp.end()) mp[x] = ind, ind++;
            else {
                length_of_loop = ind - mp[x];
                top_of_loop = mp[x];
                break;
            }
        }
    }
    ll len(){
        if (length_of_loop == -1) init();
        return length_of_loop;
    }
    ll top(){
        if (top_of_loop == -1) init();
        return top_of_loop;
    }
    T get(ll n){
        assert(0 <= n);
        if (n < top()) return vec[n];
        ll d = n - top();
        return vec[top() + (d % len())];
    }
};


int main(){
    int n, k; cin >> n >> k;
    vector<int> a(n); cin >> a;
    vector<vector<int>> dp(n+1,vector<int>(k+1,0));
    dp[0][0] = 1;
    rep(i,n){
        rep(j,k+1){
            chmax(dp[i+1][j],dp[i][j]);
            if (j + a[i] < k+1) chmax(dp[i+1][j + a[i]],dp[i][j]);
        }
    }
    vector<vector<int>> ep(n+1,vector<int>(k+1,0));
    ep[n][0] = 1;
    repb(i,n){
        rep(j,k+1){
            chmax(ep[i][j],ep[i+1][j]);
            if (j + a[i] < k+1) chmax(ep[i][j + a[i]],ep[i+1][j]);
        }
    }
    dame(dp[n][k] == 1, -1);
    int ans = 0;
    rep(i,n){
        bool t = true;
        rep(j,k+1) if (dp[i][j] + ep[i+1][k-j] == 2) t = false;
        if (t) ans++;
    }
    o(ans);
}
0