結果
問題 |
No.115 遠足のおやつ
|
ユーザー |
![]() |
提出日時 | 2019-11-25 20:38:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 899 bytes |
コンパイル時間 | 1,814 ms |
コンパイル使用メモリ | 164,112 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-01-03 01:48:32 |
合計ジャッジ時間 | 3,288 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0; i < (n);i++) #define sz(x) int(x.size()) typedef long long ll; typedef pair<int,int> P; int dp[110][1010][12]; int main(){ int n, d, K; cin >> n >> d >> K; rep(i,n+1) dp[i][0][0] = 1; rep(i,n+1) { rep(j,d+1) { rep(k,K+1) { if (dp[i][j][k]) { dp[i+1][j+i+1][k+1] = 1; dp[i+1][j][k] = 1; } } } } if (!dp[n][d][K]) { cout << -1 << endl; return 0; } vector<int> res; int s = n, cnt = K, sum = d; while (sum) { for (int i = s; i > 0; i--) { if (sum >= i) { if (dp[i-1][sum-i][cnt-1]) { s = i-1; cnt--; sum -= i; res.push_back(i); break; } } } } reverse(res.begin(), res.end()); for (auto e : res) cout << e << " "; cout << endl; return 0; }