結果
問題 | No.1532 Different Products |
ユーザー |
👑 ![]() |
提出日時 | 2021-06-04 20:27:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 897 ms / 4,000 ms |
コード長 | 1,001 bytes |
コンパイル時間 | 1,145 ms |
コンパイル使用メモリ | 75,552 KB |
最終ジャッジ日時 | 2025-01-21 22:03:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 62 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; using ull = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) ll N, K; vector<ll> dp_fairy; vector<ll> dp_devil; int main(){ cin >> N >> K; ll fairy_count = min(K,100000ll); dp_fairy.assign(fairy_count+1,0); ll devil_count = (K+fairy_count-1) / fairy_count; dp_devil.assign(devil_count+1,0); dp_devil[1] = 1; for(int a=1; a<=N; a++){ for(ll i=a; i<=fairy_count; i++){ dp_fairy[i/a] += dp_fairy[i]; } for(ll i=devil_count; i>=1; i--){ if(i*a <= devil_count) dp_devil[i*a] += dp_devil[i]; else dp_fairy[K/(i*a)] += dp_devil[i]; } } ll ans = 0; for(ll i=1; i<=fairy_count; i++) ans += dp_fairy[i]; for(ll i=0; i<=devil_count; i++) ans += dp_devil[i]; cout << (ans-1) << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;