結果
問題 |
No.115 遠足のおやつ
|
ユーザー |
|
提出日時 | 2015-12-20 14:19:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 16 ms / 5,000 ms |
コード長 | 1,497 bytes |
コンパイル時間 | 1,656 ms |
コンパイル使用メモリ | 161,964 KB |
実行使用メモリ | 18,808 KB |
最終ジャッジ日時 | 2025-01-03 01:09:24 |
合計ジャッジ時間 | 3,345 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define GET_MACRO(a, b, c, NAME, ...) NAME #define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define rep2(i, a) rep3 (i, 0, a) #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__) #define repr2(i, a) repr3 (i, 0, a) #define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--) template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); } template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } using ll = long long; bool dp[111][1010][11]; tuple<int, int, bool> pre[111][1010][11]; int main() { int N, D, K; cin >> N >> D >> K; rep (i, 111) rep (j, 1010) rep (k, 11) pre[i][j][k] = make_tuple(-1, -1, false); dp[0][0][0] = true; rep (i, N) rep (j, D + 1) rep (k, K + 1) { if (chmax(dp[i + 1][j][k], dp[i][j][k])) { pre[i + 1][j][k] = make_tuple(j, k, false); } if (j + i + 1 <= D && k + 1 <= K){ if (chmax(dp[i + 1][j + i + 1][k + 1], dp[i][j][k])) { pre[i + 1][j + i + 1][k + 1] = make_tuple(j, k, true); } } } vector<int> ans; tuple<int, int, bool> curr(D, K, false); repr (i, N) { if (get<2>(pre[i + 1][get<0>(curr)][get<1>(curr)])) { ans.push_back(i + 1); } curr = pre[i + 1][get<0>(curr)][get<1>(curr)]; } if (ans.empty()) ans.push_back(-1); reverse(ans.begin(), ans.end()); rep (i, ans.size()) cout << ans[i] << " "; cout << endl; return 0; }