結果
問題 |
No.3030 Kruskal-Katona
|
ユーザー |
|
提出日時 | 2025-02-21 21:41:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 915 bytes |
コンパイル時間 | 3,581 ms |
コンパイル使用メモリ | 282,096 KB |
実行使用メモリ | 35,072 KB |
最終ジャッジ日時 | 2025-02-21 21:41:53 |
合計ジャッジ時間 | 5,455 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<(b);i++) #define all(a) begin(a),end(a) #define sz(a) (int)(a).size() typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); ll N,i;cin>>N>>i; if(i==1){cout<<N<<endl;return 0;} if(i==2){ ll m=2; while((m+1)*m/2<=N)m++; if(N!=m*(m-1)/2)cout<<m<<" "<<N-(m-1)*m/2<<endl; else cout<<m<<endl; return 0; } vector<vector<ll>>binom(2010,vector<ll>(2010)); binom[0][0]=1; rep(i,0,2009)rep(j,0,i+1){ binom[i+1][j]+=binom[i][j]; binom[i+1][j+1]+=binom[i][j]; binom[i+1][j]=min(N+100,binom[i+1][j]); binom[i+1][j+1]=min(N+100,binom[i+1][j+1]); } vector<int>ans; while(N){ int m=i; while(binom[m][i]<=N)m++; m--; ans.emplace_back(m); N-=binom[m][i]; i--; } rep(i,0,sz(ans))cout<<ans[i]<<(i==sz(ans)-1?"\n":" "); }