#750148 (C++17) No.3090 Knapsack Function

提出ソース

結果

問題	No.3090 Knapsack Function
ユーザー	Yourein
提出日時	2022-04-01 21:27:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	81 ms / 2,000 ms
コード長	6,381 bytes
コンパイル時間	1,249 ms
コンパイル使用メモリ	121,384 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-20 08:09:34
合計ジャッジ時間	2,491 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	52 ms 6,820 KB
testcase_17	AC	81 ms 6,816 KB
testcase_18	AC	79 ms 6,816 KB
testcase_19	AC	45 ms 6,816 KB
testcase_20	AC	80 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <numeric>
#include <cassert>

//Binary Indexed Tree
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;
//Binary Indexed Tree

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using namespace std;

#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

//iostream operator
template <typename T> istream &operator>>(istream &is, vector<T> &x){for (auto &y:x){is >> y;} return is;}
template <typename T> ostream &operator<<(ostream &os, vector<T> &x){
    for (long long e = 0; e < (int)x.size(); e++){
        if (e == (int)x.size()-1) os << x[e];
        else os << x[e] << " ";
    }
    return os;
}
template <class T, class S> istream &operator>>(istream &is, pair<T, S> &x){is >> x.first >> x.second; return is;}
template <class T, class S> ostream &operator<<(ostream &os, pair<T, S> &x){os << x.first << " " << x.second; return os;}
//iostream operator

template<typename T> vector<T> reversed(vector<T> ary){int n = ary.size(); for (int i = 0; i <= n/2; i++) swap(ary[i], ary[n-i-1]); return ary;}
template<typename string> string reversed(string ary){int n = ary.size(); for (int i = 0; i <= n/2; i++) swap(ary[i], ary[n-i-1]); return ary;}

namespace cpio{
    std::ostream &operator<<(std::ostream &dest, __int128_t value) {
        std::ostream::sentry s(dest);
        if (s) {
            __uint128_t tmp = value < 0 ? -value : value;
            char buffer[128];
            char *d = std::end(buffer);
            do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10;} while (tmp != 0);
            if (value < 0) {--d; *d = '-';}
            int len = std::end(buffer) - d;
            if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}
        }
        return dest;
    }

    __int128 parse(string &s) {
        __int128 ret = 0;
        for (int i = 0; i < (int)s.length(); i++) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0';
        return ret;
    }

    std::istream &operator>>(std::istream &is, __int128_t &value){
        string temp; cin >> temp;
        value = parse(temp);
        return is;
    }

    //Debug out
    void dout(){cerr << "\n";}
    template<typename T, typename... Ts> void dout(const T& a, const Ts&... b){cerr << a; (cerr << ... << (cerr << ' ', b)); cerr << "\n";}

    //Yes or No
    void yon(bool yorn, string Y = "Yes", string N = "No"){cout << (yorn?Y:N) << endl;}
} using namespace cpio;

namespace cpmath{
    //Math library for Competitive-Programming
    constexpr const ll mod97 = 1000000007;
    constexpr const ll mod99 = 1000000009;
    constexpr const ll mod89 = 998244353;
    constexpr double pi = acos(-1);

    constexpr const int DX4[4] = {1, 0, -1, 0};
    constexpr const int DY4[4] = {0, 1, 0, -1};
    constexpr const int DX8[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    constexpr const int DY8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

    ll factorial(ll a, ll b = -1, const ll fmod = -1){
        ll ans = 1;
        if (fmod > 1) {
            if (b == -1) for (ll i = a; i > 1; i--) ans = ((ans%fmod)*(i%fmod))%fmod;
            else for (ll i = a; i >= b; i--) ans = ((ans%fmod)*(i%fmod))%fmod;
        }
        else{
            if (b == -1) for (ll i = a; i > 1; i--) ans = ans*i;
            else for(ll i = a; i >= b; i--) ans = ans*i;
        }
        return ans;
    }

    ll fastpow(ll m, ll p){
        if (p == 0) return 1;
        if (p%2 == 0){ll t = fastpow(m, p/2); return t*t;}
        return m*fastpow(m, p-1);
    }

    ll modpow(ll m, ll p, const ll fmod){
        if (p == 0) return 1;
        if (p%2 == 0){ll t = modpow(m, p/2, fmod); return (t*t)%fmod;}
        return (m*modpow(m, p-1, fmod))%fmod;
    }

    ld dtor(const ld deg){return deg*(pi/(ld)180);}

    //WARNING : Unstable function
    //TODO! : Rewrite for stabillity
    string basen(ll raw, int to){
        char c[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
        string res = "";

        while(raw){
            res.push_back(c[raw%to]);
            raw/=to;            
        }

        reverse(res.begin(), res.end());
        return res;
    }

    template<long long mod = cpmath::mod97>
    class modint{
    private:
        long long num;
    public:
        //Constructer
        modint(): num(0LL){}
        modint(long long n){num = static_cast<ll>(n);} 
        //Constructer:END
    
        modint &operator+(modint right){num = ((num+right.raw())%mod+mod)%mod; return *this;}
        modint &operator+(long long x){num = ((num+x)%mod+mod)%mod; return *this;}
        modint &operator-(modint right){num = ((num-right.raw())%mod+mod)%mod; return *this;}
        modint &operator-(long long x){num = ((num-x)%mod+mod)%mod; return *this;}
        modint &operator*(modint right){num = ((num*right.raw())%mod+mod)%mod; return *this;}
        modint &operator*(long long x){num = ((num*x)%mod+mod)%mod; return *this;}
        modint &operator/(modint right){return *this * this->inversed(right.raw());}
        modint &operator/(long long x){return *this * this->inversed(x);}

        modint &operator=(long long x){num = x; return *this;}
        friend ostream& operator<<(ostream &os, modint o){os << o.raw(); return os;}
        friend istream& operator>>(istream &is, modint &i){long long t; cin >> t; i = t; return is;}

        long long inversed(ll n){return cpmath::modpow(n, mod-2, mod);}
           long long raw(){return this->num;}
    }; //modint
}

using cpmath::mod89;
using cpmath::mod97;
using cpmath::mod99;
using cpmath::modint;

//using cpmath::DX4;
//using cpmath::DY4;
//using cpmath::DX8;
//using cpmath::DY8;

//GNU Binary Indexed Tree
// template<typename T>
// using gtree = tree<T, null_type, greater<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        int vi, wi;
        cin >> vi >> wi;
        if (wi == 1){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}

yukicoder

結果

テストケース

ソースコード