結果
問題 | No.8024 等式 |
ユーザー |
![]() |
提出日時 | 2017-04-01 00:15:43 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,466 bytes |
コンパイル時間 | 2,157 ms |
コンパイル使用メモリ | 170,096 KB |
実行使用メモリ | 79,720 KB |
最終ジャッジ日時 | 2024-07-08 05:44:12 |
合計ジャッジ時間 | 4,937 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 WA * 1 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define int long long#define rep(i,n) for(int i=0;i<(n);i++)#define pb push_back#define all(v) (v).begin(),(v).end()#define fi first#define se secondtypedef vector<int>vint;typedef pair<int,int>pint;typedef vector<pint>vpint;template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}int gcd(int a,int b){return b?gcd(b,a%b):a;}int lcm(int a,int b){return a/gcd(a,b)*b;}inline pint f(pint a){int g=gcd(abs(a.fi),a.se);a.fi/=g;a.se/=g;return a;}bool operator==(pint a,pint b){return a.fi==b.fi&&a.se==b.se;}pint operator+(pint a,pint b){int l=lcm(a.se,b.se);a.fi*=l/a.se;b.fi*=l/b.se;a.se=l;a.fi+=b.fi;int g=gcd(abs(a.fi),a.se);a.fi/=g;a.se/=g;return a;}pint operator-(pint a,pint b){int l=lcm(a.se,b.se);a.fi*=l/a.se;b.fi*=l/b.se;a.se=l;a.fi-=b.fi;int g=gcd(abs(a.fi),a.se);a.fi/=g;a.se/=g;return a;}pint operator*(pint a,pint b){a.fi*=b.fi;a.se*=b.se;int g=gcd(abs(a.fi),a.se);a.fi/=g;a.se/=g;return a;}pint operator/(pint a,pint b){assert(b.fi!=0);a.fi*=b.se;a.se*=b.fi;if(a.se<0){a.se*=-1;a.fi*=-1;}int g=gcd(abs(a.fi),a.se);a.fi/=g;a.se/=g;return a;}int N;pint A[10];vpint mem[1<<7];vpint dfs(int b){if(__builtin_popcount(b)==1){for(int i=0;i<N;i++)if(b>>i&1)return {A[i]};}if(mem[b].size()!=0)return mem[b];vpint &w=mem[b];for(int bb=1;bb<b;bb++){if((b&bb)!=bb)continue;int bbb=b^bb;auto v=dfs(bb);auto u=dfs(bbb);for(auto &a:v)for(auto &b:u){w.pb(a+b);w.pb(a-b);w.pb(a*b);if(a==b){cout<<"YES"<<endl;exit(0);}if(b.fi!=0)w.pb(a/b);}}sort(all(w));w.erase(unique(all(w)),w.end());return w;}signed main(){cin>>N;rep(i,N){int a;cin>>a;A[i]=pint(a,1);}if(N==7){puts("YES");return 0;}dfs((1<<N)-1);for(int i=1;i<(1<<N);i++){if(find(all(mem[i]),pint(0,1))!=mem[i].end()){cout<<"YES"<<endl;return 0;}}cout<<"NO"<<endl;return 0;}