#867882 (C++23) No.2093 Shio Ramen

提出ソース
結果

問題	No.2093 Shio Ramen
ユーザー	VvyLw
提出日時	2023-05-10 18:32:29
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	9 ms / 2,000 ms
コード長	16,872 bytes
コンパイル時間	3,031 ms
コンパイル使用メモリ	261,036 KB
実行使用メモリ	11,264 KB
最終ジャッジ日時	2024-05-05 05:18:03
合計ジャッジ時間	4,334 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	3 ms 5,632 KB
testcase_10	AC	8 ms 9,600 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	5 ms 8,320 KB
testcase_13	AC	5 ms 8,832 KB
testcase_14	AC	6 ms 9,472 KB
testcase_15	AC	7 ms 9,216 KB
testcase_16	AC	4 ms 5,376 KB
testcase_17	AC	8 ms 11,008 KB
testcase_18	AC	9 ms 11,136 KB
testcase_19	AC	9 ms 11,008 KB
testcase_20	AC	7 ms 11,136 KB
testcase_21	AC	8 ms 11,136 KB
testcase_22	AC	8 ms 11,136 KB
testcase_23	AC	9 ms 11,136 KB
testcase_24	AC	9 ms 11,136 KB
testcase_25	AC	8 ms 11,136 KB
testcase_26	AC	8 ms 11,136 KB
testcase_27	AC	8 ms 11,264 KB
testcase_28	AC	9 ms 11,136 KB
testcase_29	AC	8 ms 11,136 KB
testcase_30	AC	9 ms 11,264 KB
権限があれば一括ダウンロードができます
ソースコード

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

// --------------------------------------------------------------------------------------------------------------

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

namespace VvyLw {
namespace Twitter {
void wa_haya_exe(){ cin.tie(nullptr); ios::sync_with_stdio(false); }
}
void solve();
}; // VvyLw

mt19937 Random() {
    random_device seed_gen;
    mt19937 engine {seed_gen()};
    return engine;
}

// --------------------------------------------------------------------------------------------------------------

template <class T> using V = vector<T>;
template <class T, class U> using P = pair<T,U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqr = priority_queue<T,V<T>,greater<T>>;
template <class T, class U> using pqs = priority_queue<P<T,U>>;
template <class T, class U> using pqrs = priority_queue<P<T,U>,V<P<T,U>>,greater<P<T,U>>>;
template <class T, class U> bool chmax(T& a, const U& b) { if (a<b) { a=b; return 1; } return 0; }
template <class T, class U> bool chmin(T& a, const U& b) { if (a>b) { a=b; return 1; } return 0; }
template <class T, class U> inline bool overflow_if_add(T a, U b) { return (numeric_limits<T>::max()-a)<b; }
template <class T, class U> inline bool overflow_if_mul(T a, U b) { return (numeric_limits<T>::max()/a)<b; }
using ll = long long;
using ld = long double;
using uint = unsigned;
using ul = unsigned long long;
using vi = V<ll>;
using vu = V<ul>;
using vd = V<ld>;
using vc = V<char>;
using vs = V<string>;
using vb = V<bool>;
using wi = V<vi>;
using wu = V<vu>;
using wd = V<vd>;
using wc = V<vc>;
using ws = V<vs>;
using wb = V<vb>;
using pi = P<ll,ll>;
using pd = P<ld,ld>;
using pc = P<char,char>;
using ps = P<string,string>;
const int MOD = 998244353;
const int M0D = 1000000007;
const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const ld DINF = numeric_limits<ld>::infinity();
const double PI = acos(-1);
const double E = 2.718281828459045;

#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0; i<n; ++i)
#define rep2(i,n) for(ll i=0; i<n; ++i)
#define rep3(i,a,b) for(ll i=a; i<b; ++i)
#define rep4(i,a,b,c) for(ll i=a; i<b; i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rvp1(n) for(ll i=n-1; i>=0; i--)
#define rvp2(i,n) for(ll i=n-1; i>=0; i--)
#define rvp3(i,a,b) for(ll i=b-1; i>=a; i--)
#define rvp4(i,a,b,c) for(ll i=b-1; i>=a; i-=c)
#define rvp(...) overload4(__VA_ARGS__,rvp4,rvp3,rvp2,rvp1)(__VA_ARGS__)
#define all1(v) v.begin(),v.end()
#define all2(v,a) v.begin(),v.begin()+a
#define all3(v,a,b) v.begin()+a,v.begin()+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(v) v.rbegin(),v.rend()
#define rall2(v,a) v.rbegin(),v.rbegin()+a
#define rall3(v,a,b) v.rbegin()+a,v.rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define each1(elem,v) for(auto &elem: v)
#define each2(x,y,v) for(auto &[x,y]: v)
#define each3(x,y,z,v) for(auto &[x,y,z]: v)
#define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__)
#define sqrp1(n) for(ll i=0; i*i<n; ++i)
#define sqrp2(i,n) for(ll i=0; i*i<n; ++i)
#define sqrp3(i,a,b) for(ll i=a; i*i<b; ++i)
#define sqrp(...) overload3(__VA_ARGS__,sqrp3,sqrp2,sqrp1)(__VA_ARGS__)
#define irp(it,v) for(auto it=v.begin(); it!=v.end(); ++it)
#define ir(it,v) for(auto it=v.begin(); it!=v.end();)
#define FE(v,f) for_each(all(v),f)

namespace IO {
template <class T> void scan(T& a){ cin >> a; }
template <class T, class U> void scan(P<T,U>& p){ scan(p.first); scan(p.second); }
template <class T> void scan(V<T>& a){ for(auto &i: a) scan(i); }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
template <class T> void print(const T& a){ cout << a; }
template <class T, class U> void print(const P<T,U>& p){ print(p.first); cout<<" "; print(p.second); }
template <class T> void print(const V<T>& a){ if(!a.empty()){ print(a[0]); for(auto i=a.begin(); ++i!=a.end();){ cout<<" "; print(*i); } } }
template <class T> void print(const set<T>& a){ if(!a.empty()){ print(*a.begin()); for(auto i=next(a.begin()); ++i!=a.end();){ cout<<" "; print(*i); } } }
void out(){ cout<<'\n'; }
template <class T> void out(const T& t){ print(t); cout<<'\n'; }
template <class Head, class... Tail> void out(const Head& head, const Tail&... tail) { print(head); cout<<" "; out(tail...); }
template <class T> void vout(V<T>& v) { FE(v,[](T x){out(x);}); }
void fix(short x){ cout << fixed << setprecision(x); }
void Flush(){ flush(cout); }
}; // IO
using namespace IO;
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define UL(...) ul __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type,name,size) V<type> name(size); in(name)
#define WEC(type,name,h,w) V<V<type>> name(h,V<type>(w)); in(name)
#define fin(...) { out(__VA_ARGS__); return; }

namespace yesno_sys {
inline void YES(bool ok=1) { out(ok?"YES":"NO"); }
inline void NO(bool ok=1) { YES(!ok); }
inline void Yes(bool ok=1) { out(ok?"Yes":"No"); }
inline void No(bool ok=1) { Yes(!ok); }
inline void yes(bool ok=1) { print(ok?"yes":"no"); }
inline void no(bool ok=1) { yes(!ok); }
template <class Boolean> inline void yn(Boolean ok, string yes, string no){ out(ok?yes:no); }
}; // yesno_sys
using namespace yesno_sys;

namespace zia_qu {
template <class T> inline void rev(T& v){ reverse(all(v)); }
template <class T> inline void Sort(T& v){ sort(all(v)); }
template <class T> inline void Sortt(T& v){ sort(rall(v)); }
template <class T> inline void Sorth(T& v){ make_heap(all(v)); sort_heap(all(v)); }
template <class T> inline T Min(const V<T>& v){ return *min_element(all(v)); }
template <class T> inline T Max(const V<T>& v){ return *max_element(all(v)); }
template <class T, class I> inline ll dst(T& v, I itr){ return distance(v.begin(),itr); }
template <class T, class U> inline ll LB(const V<T>& v, const U x){ return dst(v,lower_bound(all(v),x)); }
template <class T, class U> inline ll UB(const V<T>& v, const U x){ return dst(v,upper_bound(all(v),x)); }
template <class T> inline bool BS(const V<T>& v, ll x){ return binary_search(all(v),x); }
template <class T, class Boolean> inline bool BS(const V<T>& v, ll x, Boolean fn){ return binary_search(all(v),x,fn); }
template <class T, class Boolean> inline bool All(const T& v, Boolean fn){ return all_of(all(v),fn); }
template <class T, class Boolean> inline bool Exist(const T& v, Boolean fn){ return any_of(all(v),fn); }
template <class T, class Boolean> inline void pt(T& v, Boolean fn){ partition(all(v),fn); }
template <class T, class Boolean> inline ll ptp(T& v, Boolean fn){ return dst(v,partition_point(all(v),fn)); }
template <class T, class U> inline ll Find(T& v, const U x){ auto itr=find(all(v),x); if(itr==v.end()) return -1LL; return dst(v,itr); }
template <class T, class U> inline void rpl(T& v, U fn, U r){ replace(all(v),fn,r); }
template <class T, class Boolean, class U> inline void rplif(T& v, Boolean fn, U r){ replace_if(all(v),fn,r); }
template <class T, class Boolean> inline ul cntif(T& v, Boolean fn){ return count_if(all(v),fn); }
template <class T> inline T Count(V<T>& v, ll x) { Sort(v); return UB(v,x)-LB(v,x); }
template <class T> inline V<T> iot(T n, ll init){ V<T> a(n); iota(all(a),init); return a;}
template <class T, class U> inline void ers(T& v, U x){ v.erase(remove(all(v),x),v.end()); }
template <class T> inline ul unq(T& v){ Sort(v); v.erase(unique(all(v)),v.end()); return v.size(); }
template <class T> inline bool eql(const T& v, const T& w){ return (v.size()==w.size() && equal(all(v),w.begin())); }
template <class T> inline T cp(const T& v){ T res; copy(all(v),back_inserter(res)); return res; }
template <class T> inline void rtt(T& s, ul idx){ rotate(all(s,idx),s.end()); }
template <class T> inline V<T> psum(V<T>& v) {
    V<T> s(v.size()+1);
    partial_sum(all(v),s.begin());
    rtt(s,v.size());
    return s;
}
template <class T> inline V<T> adf(V<T>& v){ V<T> res(v.size()-1); adjacent_difference(all(v),res.begin()); return res; }
#ifdef local
#define rext(...) static_cast<vi>(0)
template <class T> inline ll vsum(V<T> &v){ return accumulate(all(v),0LL); }
template <class T> inline ll vsum(V<T> &v, ll a, ll b){ return accumulate(all(v,a,b),0LL); }
template <class T> inline ld vdsum(V<T> &v){ return accumulate(all(v),0.0L); }
template <class T> inline ld vdsum(V<T> &v, ll a, ll b){ return accumulate(all(v,a,b),0.0L); }
template <class T> inline ll vmul(V<T> &v){ return accumulate(all(v),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ll vmul(V<T> &v, ll a, ll b){ return accumulate(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(V<T> &v){ return accumulate(all(v),1.0L,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(V<T> &v, ll a, ll b){ return accumulate(all(v,a,b),1.0L,[](ll acc,ll i){ return acc*i; }); }
#else
template <class T> inline V<T> rext(V<T>& v, ll size, mt19937 eng){ V<T> res; sample(all(v),back_inserter(res),size,eng); return res; }
template <class T> inline T rext(V<T>& v, mt19937 eng){ V<T> res; sample(all(v),back_inserter(res),1,eng); return res.front(); }
template <class T> inline ll vsum(V<T> &v){ return reduce(all(v),0LL); }
template <class T> inline ll vsum(V<T> &v, ll a, ll b){ return reduce(all(v,a,b),0LL); }
template <class T> inline ld vdsum(V<T> &v){ return reduce(all(v),0.0L); }
template <class T> inline ld vdsum(V<T> &v, ll a, ll b){ return reduce(all(v,a,b),0.0L); }
template <class T> inline ll vmul(V<T> &v){ return reduce(all(v),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ll vmul(V<T> &v, ll a, ll b){ return reduce(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(V<T> &v){ return reduce(all(v),1.0L,[](ll acc,ll i){ return acc*i; }); }
template <class T> inline ld vdmul(V<T> &v, ll a, ll b){ return reduce(all(v,a,b),1.0L,[](ll acc,ll i){ return acc*i; }); }
#endif
}; // zia qu

#ifdef local
#define debug(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); }
#else
#define debug(...) void(0);
#endif
#define strpb(s,c) s.push_back((char)(c))
#define elif else if
#define scp(a,x,b) a<=x&&x<=b
#define each_idx(el,v) &el-&v[0]
#define mp make_pair
#define mt make_tuple
#define bif(bit,tar) (tar>>bit)&1
#define nxp(x) next_permutation(all(x))
#define prp(x) prev_permutation(all(x))
#define strpl(s,a,b) regex_replace(s,regex(a),b)
#define rgxmt(s,rgx) regex_match(s,regex(rgx))
namespace Lady_sANDy {
inline ll sqr(ll x){ return x*x; }
inline ll cbc(ll x){ return x*x*x; }
inline ll Mod(ll x, ll m){ return (x+m)%m; }
inline ul Pow(ul a, uint b) { 
    ul res=1;
    while(b>0) {
        if(b&1) res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
inline ll Ceil(ld x, ll m){ return ceil(x/m); }
inline ld Round(ld x, ll m, uint fx){ if(fx==0) return (ll)round(x/m); else { ul y=Pow(10,fx+1); return round((x*y)/m/y); } }
inline ld Log(ll x, int e){ return log(x)/log(e); }
template <class T> inline T IP(const V<T>& v, const V<T>& u, T init){ return inner_product(all(v),u.begin(),init); }
inline int bitdigit(ll x){ return 64-__builtin_clzll(x); }
inline int popcnt(ll x){ return __builtin_popcountll(x); }
inline bool popcnt_OE(ll x){ return __builtin_parityll(x); }
string to_hex(ll x) {
    stringstream ss;
    ss<<hex<<x;
    string s=ss.str();
    //rep(s.size()) if(islower(s[i])) s[i]=toupper(s[i]);
    return s;
}
string to_oct(ll x) {
    stringstream s;
    s<<oct<<x;
    return s.str();
}
string to_bin(ll x) {
    stringstream s;
    s<<bitset<64>(x);
    return s.str();
}
inline vi ten_to_adic(ll m, ll n) {
    vi res;
    ll now=m;
    while(now!=0) {
        res.emplace_back(now%n);
        now/=n;
    }
    //rev(res);
    return res;
}
inline ll adic_to_ten(vi &v, ll u) {
    ll res=0;
    //rev(v);
    each(el,v) {
        ll idx=each_idx(el,v);
        res+=Pow(u,idx)*el;
    }
    return res;
}
template<class... T> constexpr auto symin(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); }
template<class... T> constexpr auto symax(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); }
template <class T, class U> inline T kymin(const map<T,U> m){ return m.begin()->first; }
template <class T, class U> inline T kymax(const map<T,U> m){ return m.rbegin()->first; }
template <class T, class U> inline U kymin_v(const map<T,U> m){ return m.begin()->second; }
template <class T, class U> inline U kymax_v(const map<T,U> m){ return m.rbegin()->second; }
template<class T, class U> inline U vlmin(map<T,U> &m){
    auto pr = *min_element(all(m),[](P<T,U> const &x, P<T,U> const &y){ return x.second > y.second; });
    return pr.second;
}
template<class T, class U> inline U vlmax(map<T,U> &m){
    auto pr = *max_element(all(m),[](P<T,U> const &x, P<T,U> const &y){ return x.second < y.second; });
    return pr.second;
}
template<class T, class U> inline T vlmin_k(map<T,U> &m){
    auto pr = *min_element(all(m),[](P<T,U> const &x, P<T,U> const &y){ return x.second > y.second; });
    return pr.first;
}
template<class T, class U> inline T vlmax_k(map<T,U> &m){
    auto pr = *max_element(all(m),[](P<T,U> const &x, P<T,U> const &y){ return x.second < y.second; });
    return pr.first;
}
template <class T> inline T stmin(set<T> s){ return *s.begin(); }
template <class T> inline T stmax(set<T> s){ return *s.rbegin(); }
}; // Lady s&y

namespace Heileden {
/* BFS Sample
template <class T> inline void bfs(V<V<T>>& g, T start, vb& visited) {
    queue<T> que;
    que.emplace(start);
    visited[start]=1;
    while(!que.empty()) {
        T v=que.front();
        que.pop();
        each(nv,g[v]) {
            if(!visited[nv]) {
                visited[nv]=1;
                que.emplace(nv);
            }
        }
    }
}//*/

/* DFS Sample
template <class T> inline void dfs(V<V<T>>& g, T v, vb& visited) {
    visited[v]=1;
    each(nv,g[v]) if(!visited[nv]) dfs(g,nv,visited);
}//*/

/* Permutation Sample
template <class T> inline void nPr(V<T>& v) {
    Sort(v);
    do {out(v);} while(nxp(v));
}//*/

/* Binary Search Sample
template <class T, class U> inline ll bns(T v, U x, ll& ng, ll& ok) {
    while(ok-ng>1) {
        ll mid = (ok+ng)/2;
        if(x==v[mid]) return mid;
        elif(x<v[mid]) ng=mid;
        else ok=mid;
    }
    if(x==v[ok]) return ok;
    return -1;
}//*/

/* Dijikstra-like Sample
template <class T> inline T dijikstra(const V<T>& v) {
    pqr<T> pq;
    T res=0;
    while(!pq.empty()) {
        each(el,v) pq.emplace(el+res);
        res=pq.top();
        pq.pop();
    }
    return res;
}//*/

// divisor
template <class T> inline V<T> divisor(T n) {
    V<T> div;
    sqrp(i,1,n+1) {
        if(n%i==0) {
            div.emplace_back(i);
            if(i*i!=n) div.emplace_back(n/i);
        }
    }
    Sort(div);
    return div;
}

// prime judge
inline bool is_prime(ul n) {
    sqrp(i,2,n+1) if(n%i==0) return 0;
    return 1;
}

// Siege of Eratosthenes
inline vb SoE(ll n) {
    vb prime(n+1,1);
    if(n>=0) prime[0]=0;
    if(n>=1) prime[1]=0;
    sqrp(i,2,n+1) {
        if(!prime[i]) continue;
        rep(j,i*i,n+1,i) prime[j]=0;
    }
    return prime;
}

// prime factor
template <class T> inline V<P<T,T>> prmfct(T n) {
    V<P<T,T>> res;
    rep(i,2,n+1) {
        if(n%i!=0) continue;
        T tmp=0;
        while(n%i==0) {
            tmp++;
            n/=i;
        }
        res.emplace_back(i,tmp);
    }
    if(n!=1) res.emplace_back(n,1);
    return res;
}

// integer judge
inline bool is_int(ld n){ ll r=floor(n); return r==n; }
inline bool is_sqr(ll n){ return is_int(sqrt(n)); }

/* grundy sample
template <class T> inline bool grundy(V<T> v) {
    ll res=0;
    each(el,v) res^=el;
    return res!=0;
}//*/
}; // Heileden


// --------------------------------------------------------------------------------------------------------------

using namespace zia_qu;
using namespace Lady_sANDy;
using namespace Heileden;

int main() {
    VvyLw::Twitter::wa_haya_exe();
    /*INT(t); while(t--)//*/
    VvyLw::solve();
}

// --------------------------------------------------------------------------------------------------------------


void VvyLw::solve() {
    INT(n,i);
    VEC(pi,p,n);
    wi dp(n+1,vi(1010));
    rep(j,n) rep(k,i+1) {
        if(k-p[j].first>=0) chmax(dp[j+1][k],dp[j][k-p[j].first]+p[j].second);
        chmax(dp[j+1][k],dp[j][k]);
    }
    out(dp[n][i]);
}
yukicoder

結果

テストケース

ソースコード
