結果

問題 No.2922 Rose Garden
ユーザー jastaway【競プロ】@青復帰！！！jastaway【競プロ】@青復帰！！！
提出日時 2024-10-12 15:29:46
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 7,000 bytes
コンパイル時間 5,510 ms
コンパイル使用メモリ 314,512 KB
実行使用メモリ 814,720 KB
最終ジャッジ日時 2024-10-12 15:29:55
合計ジャッジ時間 8,123 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
// #include <boost/rational.hpp>
// using namespace boost;
// using rat = rational<long long int>;
#define ll long long
#define ld long double
#define ull uint64_t
#define pll pair<ll,ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vpll vector<pll>
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
#define vvv(T) vector<vector<vector<T>>>
using mint = modint998244353;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define maxseg(T) segtree<T, [](T x, T y){return max(x, y);}, [](){return (T)(-(1LL << 60));}>
#define minseg(T) segtree<T, [](T x, T y){return min(x, y);}, [](){return (T)((1LL << 60));}>
#define sumseg(T) segtree<T, [](T x, T y){return x + y;}, [](){return (T)(0);}>
// template<class T> using maxseg = segtree<T, [](T x, T y){return max(x, y);}, [](){return (T)(-(1 << 30));}>;
// template<class T> using minseg = segtree<T, [](T x, T y){return min(x, y);}, [](){return (T)((1 << 30));}>;
// template<class T> using sumseg = segtree<T, [](T x, T y){return x + y;}, [](){return (T)(0);}>;
// template<class T> struct v : vector<T> { using vector<T> :: vector; };
// template<class T> struct vv : vector<v<T>> { using vector<v<T>> :: vector; };
// template<class T> struct vvv : vector<vv<T>> { using vector<vv<T>> :: vector; };
template<class T> inline bool chmin(T& a, T b) {if(a > b){a = b; return true;} else {return false;}};
template<class T> inline bool chmax(T& a, T b) {if(a < b){a = b; return true;} else {return false;}};
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i,n) for(ll i = (ll)(n) - 1; i >= 0; i--)
#define REP(i, l, r) for(ll i = (ll)l; i <= (ll)(r); i++)
#define REPR(i, l, r) for(ll i = (ll)r; i >= (ll)(l); i--)
const ll inf = (1 << 30);
const ll INF = ((ll)1 << 60);
const vector<pair<ll, ll>> DIJ = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
template<class T> void out(T a){cout << a << endl;}
void out1(mint a){cout << a.val();}
template<class T> void out1(T a){cout << a;}
template<class T, class U> void out2(T a, U b){cout << a << " " << b << endl;}
template<class T, class U, class V> void out3(T a, U b, V c) {cout << a << " " << b << " " << c << endl;}
template<class T, class U> void outp(pair<T, U> a){ out1(a.first); out1(" "); out1(a.second); cout << endl; }
template<class T> void outv(T a){rep(i, a.size()){ cout << a.at(i) << " "; } cout << endl;}
template<class T> void outvmint(T a) {rep(i, a.size()) { cout << a.at(i).val() << " "; } cout << endl;}
template<class T> void outvL(T a){rep(i, a.size()){out(a.at(i));}}
template<class T> void outvLmint(T a) {rep(i, a.size()){out(a.at(i).val());}}
template<class T> void outvv(T a){rep(i, a.size()){ rep(j, a.at(i).size()){cout << a.at(i).at(j) << " "; } cout << endl; }}
template<class T> void outvp(T a){rep(i, a.size()){ out2(a.at(i).first, a.at(i).second); }}
void setpre(int a){cout << fixed << setprecision(a);}
#define outN out("No")
#define outY out("Yes")
#define outL cout << endl
#define dame(a) {out(a);return 0;}
#define All(a) (a).begin(), (a).end()
template<class T> inline void sortr(T& v){sort(All(v)); reverse(All(v));}
template<class T> inline vector<int> argsort(T V, bool rev = false){vector<int> res(V.size()); iota(res.begin(), res.end(), 0); sort(res.begin(), res.end(), [&](int x, int y){if(!rev){return V.at(x) < V.at(y);}else{return V.at(x) > V.at(y);}}); return res;}
template<class T> inline void sort_by_idx(T& V, vector<int>& I){assert(V.size() == I.size()); T tmpv = V; for(int loopi = 0; loopi < (int)I.size(); loopi++){V.at(loopi) = tmpv.at(I.at(loopi));}}
template<class T, class U> inline void sortp(vector<T>& v1, vector<U>& v2, bool rev1 = false, int rev2 = false){assert(v1.size() == v2.size()); vector<int> I(v1.size()); iota(I.begin(), I.end(), 0); sort(I.begin(), I.end(), [&](const int x, const int y){if(v1.at(x) != v1.at(y)){return (bool)(rev1 ^ (v1.at(x) < v1.at(y)));}else{if(v2.at(x)==v2.at(y)){return false;} return (bool)(rev2 ^ (v2.at(x) < v2.at(y)));}}); sort_by_idx(v1, I); sort_by_idx(v2, I);}
template<class T> T POW(T x, ll n) {T ret = 1; while(n > 0){if(n & 1) ret *= x; x *= x; n >>= 1;} return ret;}
ll powll(ll x, ll n){ll ret = 1; while(n > 0){if(n & 1) ret *= x; x *= x; n >>= 1;} return ret;}
#define cin1(n) cin >> (n)
#define cin2(n, m) cin >> (n) >> (m)
#define cin3(n, m, k) cin >> (n) >> (m) >> (k)
#define cin4(n, m, k, l) cin >> (n) >> (m) >> (k) >> (l)
#define cinv(a) rep(lopi, a.size()) cin >> (a).at(lopi)
#define cinll1(n) ll n; cin >> (n)
#define cinll2(n, m) ll n, m; cin >> (n) >> (m)
#define cinll3(n, m, k) ll n, m, k; cin >> (n) >> (m) >> (k)
#define cinll4(n, m, k, l) ll n, m, k, l; cin >> (n) >> (m) >> (k) >> (l)
#define cinvll(a, n) vll a(n); rep(lopi, (n)) cin >> (a).at(lopi)
#define cinstr(S) string S; cin >> (S)
#define cinvt(type, a, n) v(type) a(n); rep(lopi, n) cin >> (a).at(lopi)
#define makeundirGll(G, N, M) G = vvll(N); rep(lopi, M) {ll a, b; cin >> a >> b; G.at(a-1).push_back(b-1); G.at(b-1).push_back(a-1);}
#define makedirGll(G, N, M) G = vvll(N); rep(lopi, M) {ll a, b; cin >> a >> b; G.at(a-1).push_back(b-1);}
#define makeundirwghGll(G, N, M) G = vv(pll)(N); rep(lopi, M) {ll a, b, c; cin >> a >> b >> c; G.at(a-1).push_back({b-1,c}); G.at(b-1).push_back({a-1, c});}
#define makedirwghGll (G, N, M) G = vv(pll)(N); rep(lopi, M) {ll a, b, c; cin >> a >> b >> c; G.at(a-1).push_back({b-1, c});}
ll llceil(ll x, ll y) { if(x >= 0) {return(x / y + (ll)(x % y != 0)); } else { return -((-x) / y); } }
inline bool inLR(ll x, ll L, ll R){ return (L <= x && x < R); }
inline bool is_in_Rect(ll pos_x, ll pos_y, ll rect_H, ll rect_W, ll rect_h = 0, ll rect_w = 0){ return (rect_h <= pos_x && pos_x < rect_H && rect_w <= pos_y && pos_y < rect_W); }

template<class T> vector<T> &operator++(vector<T> &v) {for(auto &e : v){e++;} return v;}
template<class T> vector<T> operator++(vector<T> &v, signed) {auto res=v; for(auto &e : v){e++;} return res;}
template<class T> vector<T> &operator--(vector<T> &v) {for(auto &e : v){e--;} return v;}
template<class T> vector<T> operator--(vector<T> &v, signed) {auto res=v; for(auto &e : v){e--;} return res;}
template<class T, class U> pair<T, U> operator+(pair<T, U> &x, pair<T, U> &y) { return make_pair(x.first + y.first, x.second + y.second); }
template<class T, class U> void operator+=(pair<T, U> &x, pair<T, U> &y) { x = x + y; }

int main()
{
    std::cin.tie(nullptr), std::ios_base::sync_with_stdio(false);
    cinll3(N, S, B);
    cinvll(H, N);
    vvll dp(N, vll(S + 1, -INF));
    dp.at(0).at(0) = H.at(0);
    rep(i, N - 1) REP(s, 0, S)
    {
        if(s < S && dp.at(i).at(s) >= 0) chmax(dp.at(i).at(s + 1), dp.at(i).at(s) + B);
        if(dp.at(i).at(s) >= H.at(i + 1))
        {
            chmax(dp.at(i + 1).at(s), dp.at(i).at(s));
            chmax(dp.at(i + 1).at(0), H.at(i + 1));
        }
    }
    if(dp.at(N - 1).at(S) >= H.at(N - 1)) outY;
    else outN;
}
0