結果
問題 | No.1352 Three Coins |
ユーザー | blackyuki |
提出日時 | 2021-01-13 20:20:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 738 bytes |
コンパイル時間 | 2,079 ms |
コンパイル使用メモリ | 198,820 KB |
最終ジャッジ日時 | 2025-01-17 17:34:22 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> using namespace std; int main(){ int a,b,c;cin>>a>>b>>c; assert(1<=a&&a<=2000); assert(1<=b&&b<=2000); assert(1<=c&&c<=2000); if(__gcd(a,__gcd(b,c))!=1){ cout<<"INF"<<endl; return 0; } vector<bool> dp(10000000,false); queue<int> q; q.push(0); while(!q.empty()){ auto t=q.front();q.pop(); if(t+a<dp.size()&&!dp[t+a]){ dp[t+a]=true;q.push(t+a); } if(t+b<dp.size()&&!dp[t+b]){ dp[t+b]=true;q.push(t+b); } if(t+c<dp.size()&&!dp[t+c]){ dp[t+c]=true;q.push(t+c); } } int ans=0; for(int i=1;i<10000000;i++)if(!dp[i]){ ans++; } cout<<ans<<endl; }