fork(2) download
copy 
  1. #pragma comment(linker, "/stack:200000000")
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #pragma GCC optimize("unroll-loops")
  5.  
  6. #include<bits/stdc++.h>
  7. #include<ext/pb_ds/assoc_container.hpp>
  8. #include<ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10. using namespace std;
  11.  
  12. #define ll long long
  13. #define ull unsigned long long
  14. #define ld long double
  15. #define pii pair<int,int>
  16. #define pll pair<ll,ll>
  17. #define vi vector<int>
  18. #define vll vector<ll>
  19. #define vc vector<char>
  20. #define vs vector<string>
  21. #define vpll vector<pll>
  22. #define vpii vector<pii>
  23. #define umap unordered_map
  24. #define uset unordered_set
  25. #define PQ priority_queue
  26.  
  27. #define printa(a,L,R) for(int i=L;i<R;i++) cout<<a[i]<<(i==R-1?'\n':' ')
  28. #define printv(a) printa(a,0,a.size())
  29. #define print2d(a,r,c) for(int i=0;i<r;i++) for(int j=0;j<c;j++) cout<<a[i][j]<<(j==c-1?'\n':' ')
  30. #define pb push_back
  31. #define eb emplace_back
  32. #define mt make_tuple
  33. #define fbo find_by_order
  34. #define ook order_of_key
  35. #define MP make_pair
  36. #define UB upper_bound
  37. #define LB lower_bound
  38. #define SQ(x) ((x)*(x))
  39. #define issq(x) (((ll)(sqrt((x))))*((ll)(sqrt((x))))==(x))
  40. #define F first
  41. #define S second
  42. #define mem(a,x) memset(a,x,sizeof(a))
  43. #define inf 1e18
  44. #define E 2.71828182845904523536
  45. #define gamma 0.5772156649
  46. #define nl "\n"
  47. #define lg(r,n) (int)(log2(n)/log2(r))
  48. #define pf printf
  49. #define sf scanf
  50. #define sf1(a)                scanf("%d",&a)
  51. #define sf2(a,b)              scanf("%d %d",&a,&b)
  52. #define sf3(a,b,c)            scanf("%d %d %d",&a,&b,&c)
  53. #define pf1(a)                printf("%d\n",a);
  54. #define pf2(a,b)              printf("%d %d\n",a,b)
  55. #define pf3(a,b,c)            printf("%d %d %d\n",a,b,c)
  56. #define sf1ll(a)              scanf("%lld",&a)
  57. #define sf2ll(a,b)            scanf("%I64d %I64d",&a,&b)
  58. #define sf3ll(a,b,c)          scanf("%I64d %I64d %I64d",&a,&b,&c)
  59. #define pf1ll(a)              printf("%lld\n",a);
  60. #define pf2ll(a,b)            printf("%I64d %I64d\n",a,b)
  61. #define pf3ll(a,b,c)          printf("%I64d %I64d %I64d\n",a,b,c)
  62. #define _ccase printf("Case %lld: ",++cs)
  63. #define _case cout<<"Case "<<++cs<<": "
  64. #define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
  65.  
  66. #define asche cerr<<"Ekhane asche\n";
  67. #define rev(v) reverse(v.begin(),v.end())
  68. #define srt(v) sort(v.begin(),v.end())
  69. #define grtsrt(v) sort(v.begin(),v.end(),greater<ll>())
  70. #define all(v) v.begin(),v.end()
  71. #define mnv(v) *min_element(v.begin(),v.end())
  72. #define mxv(v) *max_element(v.begin(),v.end())
  73. #define toint(a) atoi(a.c_str())
  74. #define BeatMeScanf ios_base::sync_with_stdio(false)
  75. #define valid(tx,ty) (tx>=0&&tx<n&&ty>=0&&ty<m)
  76. #define one(x) __builtin_popcount(x)
  77. #define Unique(v) v.erase(unique(all(v)),v.end())
  78. #define stree l=(n<<1),r=l+1,mid=b+(e-b)/2
  79. #define fout(x) fixed<<setprecision(x)
  80. string tostr(int n) {stringstream rr;rr<<n;return rr.str();}
  81. inline void yes(){cout<<"YES\n";exit(0);}
  82. inline void no(){cout<<"NO\n";exit(0);}
  83. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  84. //ll dx[]={1,0,-1,0,1,-1,-1,1};
  85. //ll dy[]={0,1,0,-1,1,1,-1,-1};
  86. //random_device rd;
  87. //mt19937 random(rd());
  88. #define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); deb(_it, args); }
  89. void deb(istream_iterator<string> it) {}
  90. template<typename T, typename... Args>
  91. void deb(istream_iterator<string> it, T a, Args... args) {
  92.     cerr << *it << " = " << a << endl;
  93.     deb(++it, args...);
  94. }
  95.  
  96. const int mod=1e9+7;
  97. const int N=55;
  98. const ld eps=1e-9;
  99. const ld PI=acos(-1.0);
  100. //ll gcd(ll a,ll b){while(b){ll x=a%b;a=b;b=x;}return a;}
  101. //ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
  102. //ll qpow(ll n,ll k) {ll ans=1;assert(k>=0);n%=mod;while(k>0){if(k&1) ans=(ans*n)%mod;n=(n*n)%mod;k>>=1;}return ans%mod;}
  103.  
  104. int n,k,a[N],b[N],dp[N][510][510];
  105. bool yo(int i,int p,int f)
  106. {
  107.     if(i==n+1){
  108.         if(p==0&&f==0) return 0;
  109.         if(p/f==k) return 1;
  110.         return 0;
  111.     }
  112.     int &ret=dp[i][p][f];
  113.     if(ret!=-1) return ret;
  114.     return yo(i+1,p,f)|yo(i+1,p+a[i],f+b[i]);
  115. }
  116.  
  117. int main()
  118. {
  119.     BeatMeScanf;
  120.     int i,j,m;
  121.     cin>>n>>k;
  122.     for(i=1;i<=n;i++) cin>>a[i]>>b[i];
  123.     mem(dp,-1);
  124.     if(yo(1,0,0)) yes();
  125.     no();
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0.01s 71104KB
comments (?)
stdin
copy 
3 5
8 1
1 1
2 1
stdout
copy 
YES
https://ideone.com/ipbnWa
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!