fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int dis[50005];
  5. int n,a[5005];
  6.  
  7.  
  8. int main()
  9. {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(NULL);
  12.     cout.tie(NULL);
  13.  
  14.     cin>>n;
  15.     for(int i=0;i<n;i++)
  16.         cin>>a[i];
  17.  
  18.     for(int i=0;i<a[0];i++)
  19.         dis[i]=INT_MAX;
  20.     dis[0]=0;   // dijkstra started
  21.     set<pair<int,int> >s;
  22.     s.insert({0,0});
  23.     while(!s.empty())
  24.     {
  25.         pair<int,int> p=*s.begin();
  26.         s.erase(s.begin());
  27.         int u=p.second,w=p.first;
  28.         for(int i=1;i<n;i++)
  29.         {
  30.             int v=(u+a[i])%a[0];
  31.             if(w+a[i]<dis[v])   // w = dis[u]
  32.             {
  33.                 dis[v]=w+a[i];
  34.                 s.insert({dis[v],v});
  35.             }
  36.         }
  37.     }  //dijkstra ended
  38.     int k;
  39.     cin>>k;
  40.     while(k--)
  41.     {
  42.         int b;
  43.         cin>>b;
  44.         if(dis[b%a[0]]<=b)
  45.         {
  46.             cout<<"TAK"<<'\n';
  47.         }
  48.         else
  49.             cout<<"NIE"<<'\n';
  50.     }
  51. }
  52.  
Runtime error #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3GVmv1
language:
C++14 (gcc 8.3)
created:
7 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!