Submission #73160291

---

Source Code Expand

//  ===== ライブラリインクルード =====
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

//  ===== 型の省略名定義 =====
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vc = vector<char>;
using vvc = vector<vector<char>>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vvpii = vector<vector<pii>>;
using vpll = vector<pll>;
using vvpll = vector<vector<pll>>;
using vs = vector<string>;

//  ===== 略記用マクロ =====
#define rep(i, n) for (auto i = decltype(n){0}; i < (n); ++i)
#define rrep(i, n) for (auto i = (n); i-- > decltype(n){0}; )
#define nfor(i, l, r) for (auto i = (l); i < (r); ++i)
#define rnfor(i, l, r) for (auto i = (r); i-- > (l); )
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

//  ===== 無限大定数 =====
constexpr int INF = 1e9;
constexpr ll LINF = 4e18;

//  ===== 入出力 =====
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p)
{return os << p.first << " " << p.second;}

template <typename T>
concept HasVal = requires(T v) {{ v.val() } -> convertible_to<long long>;};
ostream& operator<<(ostream& os, HasVal auto v) {return os << v.val();}

template <class T>
void print_vector(const vector<T>& v, const string& sep = "\n", bool omit_last = false)
{
    int siz = (int)v.size();
    rep(i, siz)
    {
        cout << v[i];
        if(!(omit_last && i == siz - 1)) cout << sep;
    }
}

//  ===== 汎用関数 =====
template <class T> bool chmax(T &a, T b){ if(a<b){a=b; return true;} return false;}
template <class T> bool chmin(T &a, T b){ if(a>b){a=b; return true;} return false;}
template <class T> void dedup(vector<T>& v) {v.erase(unique(all(v)), v.end());}

//  ========== テンプレ終わり ==========



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, k;
    cin >> n >> m >> k;
    vll a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];

    //dp[i][j] : i番目の都市から出発する時点で、j円残っているような移動方法のうちの最大利益
    vvll dp(n+1, vll(m+1, -LINF));
    rep(i, n+1) dp[i][m] = 0;
    rep(i, n)
    {
        rep(d, k)
        {
            int pre_i = i - d;
            if(pre_i < 0) continue;
            
            rep(j, m+1)
            {
                if(j + b[i] <= m)
                {
                    chmax(dp[i+1][j], dp[pre_i][j + b[i]] + a[i]);
                }
            }
        }
    }

    ll ans = 0;
    rep(i, n) rep(j, m+1) chmax(ans, dp[i+1][j]);
    cout << ans << endl;
}

Submission Info

Judge Result