#823417 (C++17) No.2150 Site Supporter

提出ソース

結果

問題	No.2150 Site Supporter
ユーザー	Sarievo
提出日時	2022-12-09 00:38:49
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	37 ms / 2,000 ms
コード長	5,264 bytes
コンパイル時間	2,076 ms
コンパイル使用メモリ	201,224 KB
実行使用メモリ	14,848 KB
最終ジャッジ日時	2024-04-22 18:49:33
合計ジャッジ時間	3,416 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 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	7 ms 5,376 KB
testcase_09	AC	35 ms 13,696 KB
testcase_10	AC	18 ms 8,320 KB
testcase_11	AC	32 ms 12,928 KB
testcase_12	AC	13 ms 6,912 KB
testcase_13	AC	7 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	1 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	37 ms 14,848 KB
testcase_18	AC	16 ms 7,680 KB
testcase_19	AC	6 ms 5,376 KB
testcase_20	AC	26 ms 11,008 KB
testcase_21	AC	4 ms 5,376 KB
testcase_22	AC	34 ms 13,696 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	1 ms 5,376 KB
testcase_26	AC	1 ms 5,376 KB
testcase_27	AC	22 ms 9,472 KB
testcase_28	AC	21 ms 9,088 KB

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

ソースコード

raw source code

#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);
 *
 */
}

yukicoder

結果

テストケース

ソースコード