結果
問題 | No.2150 Site Supporter |
ユーザー | Sarievo |
提出日時 | 2022-12-09 00:38:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 5,264 bytes |
コンパイル時間 | 2,381 ms |
コンパイル使用メモリ | 207,456 KB |
実行使用メモリ | 14,848 KB |
最終ジャッジ日時 | 2024-10-14 18:20:49 |
合計ジャッジ時間 | 3,765 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 7 ms
5,248 KB |
testcase_09 | AC | 34 ms
13,568 KB |
testcase_10 | AC | 19 ms
8,320 KB |
testcase_11 | AC | 32 ms
12,996 KB |
testcase_12 | AC | 14 ms
6,912 KB |
testcase_13 | AC | 9 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 38 ms
14,848 KB |
testcase_18 | AC | 16 ms
7,808 KB |
testcase_19 | AC | 6 ms
5,248 KB |
testcase_20 | AC | 27 ms
11,008 KB |
testcase_21 | AC | 5 ms
5,248 KB |
testcase_22 | AC | 34 ms
13,696 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 22 ms
9,344 KB |
testcase_28 | AC | 22 ms
9,088 KB |
ソースコード
#line 2 "codex/template/template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3","unroll-loops") #include <bits/stdc++.h> using namespace std; // macros #line 1 "codex/template/macro.hpp" #define fi first #define se second #define overload4(a, b, c, d, e, ...) e #define overload3(a, b, c, d, ...) d #define rep1(a) for(ll i=0;i<(ll)(a);i++) #define rep2(i, a) for(ll i=0;i<(ll)(a);i++) #define rep3(i, a, b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep4(i, a, b, c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c)) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(a) for(ll i=(ll)(a)-1;i>=0;i--) #define rrep2(i, a) for(ll i=(ll)(a)-1;i>=0;i--) #define rrep3(i, a, b) for(ll i=(ll)(b)-1;i>=(ll)(a);i--) #define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__) #define fore(...) for(auto&&__VA_ARGS__) #define all(i) begin(i),end(i) #define rall(n) (n).rbegin(),(n).rend() #define ini(...) int __VA_ARGS__;in(__VA_ARGS__) #define inl(...) long long __VA_ARGS__;in(__VA_ARGS__) #define ins(...) string __VA_ARGS__;in(__VA_ARGS__) #define in2(s, t) for (int i = 0; i < (int)s.size(); i++) { in(s[i], t[i]); } #define in3(s, t, u) for (int i = 0; i < (int)s.size(); i++) { in(s[i], t[i], u[i]); } #define in4(s, t, u, v) for (int i = 0; i < (int)s.size(); i++) { in(s[i], t[i], u[i], v[i]); } #define fin(...) { out(__VA_ARGS__);return; } #line 9 "codex/template/template.hpp" // utilities #line 1 "codex/template/util.hpp" namespace Nyan { using ll = long long; using ld = long double; using vi = vector<int>; using vl = vector<ll>; using vc = vector<char>; using vs = vector<string>; using vb = vector<bool>; using vvi= vector<vi>; using vvl= vector<vl>; using vvc= vector<vc>; using pi = pair<int, int>; using pl = pair<ll, ll>; using vp = vector<pl>; template<typename T> using V = vector<T>; template<typename T> using VV = vector<vector<T>>; template<typename T, typename U> inline bool chmax(T &a, U b) { return a < b && (a = b, true); } template<typename T, typename U> inline bool chmin(T &a, U b) { return a > b && (a = b, true); } template<typename T> inline T Max(const vector<T> &v) { return *max_element(begin(v), end(v)); } template<typename T> inline T Min(const vector<T> &v) { return *min_element(begin(v), end(v)); } template<typename T> inline long long Sum(const vector<T> &v) { return accumulate(begin(v), end(v), 0LL); } template<class T> using maxheap = priority_queue<T>; template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>; constexpr ll MOD = 1000000007; constexpr ll mod = 998244353; constexpr int dx[]{+0, +1, +0, -1, +1, +1, -1, -1}; constexpr int dy[]{+1, +0, -1, +0, +1, -1, -1, +1}; void yes(bool x) { cout << (x ? "yes" : "no") << endl; } void Yes(bool x) { cout << (x ? "Yes" : "No") << endl; } void YES(bool x) { cout << (x ? "YES" : "NO") << endl; } } // namespace Nyan #line 12 "codex/template/template.hpp" // input/output #line 1 "codex/template/io.hpp" namespace Nyan { template<typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &p) { os << p.first << " " << p.second; return os; } template<typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template<typename T> ostream &operator<<(ostream &os, vector<T> &v) { for (auto it = v.begin(); it != v.end();) { os << *it << ((++it) != v.end() ? " " : ""); } return os; } template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &e : v) is >> e; return is; } void in() {} template<class T, class... U> void in(T &t, U &...u) { cin >> t; in(u...); } void out() { cout << "\n"; } template<typename T, class... U, char sep = ' '> void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } struct Nyan { Nyan() { cin.tie(nullptr); ios::sync_with_stdio(false); cout.tie(nullptr); cout << fixed << setprecision(12); cerr << fixed << setprecision(12); } } nyan; } // namespace Nyan #line 15 "codex/template/template.hpp" namespace Nyan { void solve(); } signed main() { Nyan::solve(); } /** * @brief Template(テンプレート) */ #line 2 "code.cpp" void Nyan::solve() { ini(n, k, x); vl a(n); in(a); vvl dp(n+1, vl(2, 0)); rep(i, 1, n + 1) { ll cost = a[i-1]; if (i == 1) { dp[i][0] = cost; dp[i][1] = k + x; } else { dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + cost; dp[i][1] = min(dp[i - 1][0] + (k + x), dp[i - 1][1] + k); } } out(Min(dp.back())); /* * membership per day is k + x yen * extend subscription for a day is k yen * what's the minimum cost for solving all the problems I planned * * ok, so * facts: * * 1) I didn't subscribe yesterday * - if the cost of paying individual problems is greater than k + x, than I'll subscribe, the cost is k + x * - else ? * 2) I subscribed yesterday * - if the cost of paying individual problems is greater than k, than I'll subscribe, the cost is k * * state? I subscribed yesterday / I didn't subscribe yesterday -> minimum yen needed if I subscribe or not today * trans? * dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + ai * dp[i][1] = min(dp[i-1][0] + (k + x), dp[i-1][1] + k); * */ }