結果
問題 |
No.115 遠足のおやつ
|
ユーザー |
|
提出日時 | 2020-02-01 09:32:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 2,241 bytes |
コンパイル時間 | 1,865 ms |
コンパイル使用メモリ | 163,472 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-03 01:52:43 |
合計ジャッジ時間 | 3,176 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long int ll; typedef pair<ll, ll > pi; typedef pair<pair<ll, ll >, ll > pii; vector<ll > vec; vector<ll > vec2; ll MOD = 1000000007; ll INF = 1145141919454519; //a円の商品を買ったと仮定した時,残りの金額D-a円と購入数K-1を使って //a+1~N円の商品をちょうどK-1個買えますか?を調べる //そもそも金額が小さい順にK個買った時にD円を超えると適切な選び方はないし //大きい順に買ってもD円を超えなければ適切な選び方はない ll N, D, K; bool check(ll p, ll d, ll k){ //下限 ll mn = 0; //上限 ll mx = 0; for(ll i = 0; i < k; i++){ mn += p + i; mx += N - i; } if(mn <= d && mx >= d) return true; else return false; } int main() { cin >> N >> D >> K; ll k = K; vector<ll > ans; if(check(1, D, k)){ for(ll i = 1; i <= N; i++){ if(K <= 0) break; if(check(i+1, D-i, k-1)){ ans.push_back(i); D -= i; k -= 1; } } //表示 for(ll i = 0; i < K; i++){ cout << ( i ? " " : "" ) << ans[i]; } cout << endl; }else{ cout << -1 << endl; } return 0; // for(ll k = 1; k <= N; k++){ // bool f = false; // vector<ll > ans; // ll cn = 0; // ll DD = D; // for(ll i = k; i <= N; i++){ // if(cn < K-2){ // ans.push_back(i); // DD -= i; // cn++; // }else{ // //cout << D << " " << i << endl; // if(DD - i > i && DD - i <= N ){ // ans.push_back(i); // ans.push_back(DD-i); // cn += 2; // f = true; // break; // } // } // } // if(f == true){ // for(ll i = 0; i < K; i++){ // cout << ( i ? " " : "" ) << ans[i]; // } // cout << endl; // return 0; // } // } // cout << -1 << endl; // return 0; }