#845679 (C++14) No.2232 Miser's Gift

• 問題: No.2232 Miser's Gift
• ユーザー: hamamon
• 提出日時: 2023-03-03 22:04:48
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 89 ms / 2,000 ms
• コード長: 4,787 bytes
• コンパイル時間: 5,059 ms
• コンパイル使用メモリ: 258,856 KB
• 実行使用メモリ: 83,412 KB
• 最終ジャッジ日時: 2023-10-18 02:11:17
• 合計ジャッジ時間: 10,677 ms
• ジャッジサーバーID （参考情報）: judge14 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	87 ms; 83,412 KB
testcase_04	AC	89 ms; 83,412 KB
testcase_05	AC	11 ms; 11,340 KB
testcase_06	AC	2 ms; 4,348 KB
testcase_07	AC	14 ms; 5,796 KB
testcase_08	AC	88 ms; 83,412 KB
testcase_09	AC	86 ms; 83,412 KB
testcase_10	AC	85 ms; 83,412 KB
testcase_11	AC	87 ms; 83,412 KB
testcase_12	AC	85 ms; 83,412 KB
testcase_13	AC	86 ms; 83,412 KB
testcase_14	AC	85 ms; 83,412 KB
testcase_15	AC	85 ms; 83,412 KB
testcase_16	AC	85 ms; 83,412 KB
testcase_17	AC	85 ms; 83,412 KB
testcase_18	AC	85 ms; 83,412 KB
testcase_19	AC	87 ms; 83,412 KB
testcase_20	AC	88 ms; 83,412 KB
testcase_21	AC	88 ms; 83,412 KB
testcase_22	AC	88 ms; 83,412 KB
testcase_23	AC	88 ms; 83,412 KB
testcase_24	AC	85 ms; 83,412 KB
testcase_25	AC	86 ms; 83,412 KB
testcase_26	AC	89 ms; 83,412 KB
testcase_27	AC	87 ms; 83,412 KB
testcase_28	AC	87 ms; 83,412 KB
testcase_29	AC	86 ms; 83,412 KB
testcase_30	AC	88 ms; 83,412 KB
testcase_31	AC	85 ms; 83,412 KB
testcase_32	AC	87 ms; 83,412 KB
testcase_33	AC	85 ms; 83,412 KB
testcase_34	AC	87 ms; 83,412 KB
testcase_35	AC	85 ms; 83,412 KB
testcase_36	AC	85 ms; 83,412 KB
testcase_37	AC	86 ms; 83,412 KB
testcase_38	AC	3 ms; 4,348 KB
testcase_39	AC	3 ms; 4,348 KB
testcase_40	AC	3 ms; 4,348 KB
testcase_41	AC	3 ms; 4,348 KB
testcase_42	AC	3 ms; 4,348 KB
testcase_43	AC	3 ms; 4,348 KB
testcase_44	AC	3 ms; 4,348 KB
testcase_45	AC	3 ms; 4,348 KB
testcase_46	AC	3 ms; 4,348 KB
testcase_47	AC	3 ms; 4,348 KB
testcase_48	AC	2 ms; 4,348 KB
testcase_49	AC	2 ms; 4,348 KB
testcase_50	AC	2 ms; 4,348 KB
testcase_51	AC	2 ms; 4,348 KB
testcase_52	AC	2 ms; 4,348 KB
testcase_53	AC	2 ms; 4,348 KB
testcase_54	AC	2 ms; 4,348 KB
testcase_55	AC	2 ms; 4,348 KB
testcase_56	AC	2 ms; 4,348 KB
testcase_57	AC	2 ms; 4,348 KB

ソースコード

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

#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

using LL = long long;
using VI = vector<int>;
using VL = vector<LL>;
using VS = vector<string>;
using VC = vector<char>;
using VB = vector<bool>;
using VVI = vector<vector<int>>;
using VVL = vector<vector<LL>>;
using VVS = vector<vector<string>>;
using VVC = vector<vector<char>>;
using VVB = vector<vector<bool>>;
using SI = set<int>;
using PII = pair<int, int>;
const LL LINF = 1e18;
const int IINF = 1e9;
 
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl 
#define out(a) cout << a << endl
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define rrep(i, a, b) for (int i = a; i >= (int)(b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const double PI = acos(-1);
const VI DX = {-1, 0, 1, 0};
const VI DY = {0, 1, 0, -1};

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

bool IsPrime(LL num){if (num < 2) return false; else if (num == 2) return true; else if (num % 2 == 0) return false; double sqrtNum = sqrt(num); for (int i = 3; i <= sqrtNum; i += 2) if (num % i == 0) return false; return true;}
LL fact(LL n) { LL res = 1; while (n > 1) res *= n--; return res; } //factorial
map<LL,LL> decomp(LL N){map<LL,LL> res; LL num=N; for(LL i=2;i*i<=num;i++){while(N%i==0) N/=i,res[i]++; if(N==1) break;} if(N!=1) res[N]++; return res;}
bool isNumber(string s){for(auto c : s){if (isdigit(c))continue;else return false;}return true;} //if string is number then true, otherwise false
LL n_ary_str(string s, int n){LL ans = 0; for(char x:s){ans *= n; ans += x - '0';} return ans;}
LL n_ary_VI(VI arr, int n){LL ans = 0;rep(i, 0, arr.size()){ans *= n;ans += arr[i];} return ans;}
int GCD(int a, int b){if(b==0){return a;}else{return GCD(b,a%b);}}
int LCM(int a, int b){return(a/GCD(a,b))*b;}
VI split_digit(int a){VI res;string s=to_string(a);for(auto c:s){res.push_back(c-'0');}return res;}
LL power(int a,int b){LL res=1;rep(i,0,b){res*=a;}return res;}
int ctoi(char c){return c-'0';}
VS VStrans(VS a){int h = a.size(); int w = a[0].size(); VS b(w, string(h, '?')); rep(i, 0, h){ rep(j, 0, w){b[j][i] = a[i][j];}} return b;}
VVI VVItrans(VVI a){VVI b(a.size(), VI(a[0].size())); rep(i, 0, a.size()){rep(j, 0, a[i].size()){b[j][i] = a[i][j];}} return b;}
VVC VVCtrans(VVC a){VVC b(a.size(), VC(a[0].size())); rep(i, 0, a.size()){rep(j, 0, a[i].size()) b[j][i] = a[i][j];} return b;}
int VVImin(VVI a){int res = IINF;rep(i,0,a.size()){res=min(res,*min_element(all(a[i])));}return res;}
int VVImax(VVI a){int res = 0;rep(i,0,a.size()){res=max(res,*max_element(all(a[i])));}return res;}
VL get_divisors(LL n){vector<LL>ret;for(LL i=1;i*i<=n;i++){if(n%i==0){ret.push_back(i);if(i*i!=n)ret.push_back(n/i);}}sort(ret.begin(),ret.end());return ret;}

bool Sfind(string s,string tgt){if(s.find(tgt)!=string::npos)return true;else return false;}
bool VIfind(VI a,int tgt){if(count(all(a),tgt))return true;else return false;}
bool VVIfind(VVI a,int tgt){for(auto A:a){if(VIfind(A,tgt))return true;}return false;}
bool VCfind(VC a,char tgt){if(count(all(a),tgt))return true;else return false;}
bool VVCfind(VVC a,char tgt){for(auto A:a){if(VCfind(A,tgt))return true;}return false;}
bool VSfind(VS a,string tgt){if(count(all(a),tgt))return true;else return false;}
bool VVSfind(VVS a,string tgt){for(auto A:a){if(VSfind(A,tgt))return true;}return false;}
bool VBfind(VB a,bool tgt){if(count(all(a),tgt))return true;else return false;}
bool VVBfind(VVB a,bool tgt){for(auto A:a){if(VBfind(A,tgt))return true;}return false;}

void VScout(VS a){rep(i,0,a.size()){cout<<a[i]<<endl;}}
void VIcout(VI a){rep(i,0,a.size())cout<<a[i]<<" ";cout<<endl;}
void VLcout(VL a){rep(i,0,a.size())cout<<a[i]<<" ";cout<<endl;}
void VVIcout(VVI a){rep(i,0,a.size()){VIcout(a[i]);}}
void VVLcout(VVL a){rep(i,0,a.size()){VLcout(a[i]);}}
void VCcout(VC a){rep(i,0,a.size())cout<<a[i]<<' ';cout<<endl;}
void VVCcout(VVC a){rep(i,0,a.size()){VCcout(a[i]);}}
void VBcout(VB a){rep(i,0,a.size()){if(a[i])cout<<"o ";else cout<<"x ";}cout<<endl;return;}
void VVBcout(VVB a){rep(i,0,a.size())VBcout(a[i]);return;}
void SIcout(SI st){for(auto s:st){cout<<s<<" ";}cout<<endl;}

int main() {
    int n, W; cin >> n >> W;
    VI w(n+1), v(n+1); rep(i, 1, n+1) cin >> w[i] >> v[i];
    VVL dp(n+1, VL(W+1, 0));
    rep(i, 1, n+1){
        rep(j, 0, W+1){
            dp[i][j] = dp[i-1][j];
            if(j-w[i] >= 0){
                chmax(dp[i][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }
    rep(x, 1, W+1){
        printf("%lld\n",dp[n][W] - dp[n][W-x] + 1);
    }
    return 0;
}