fork(1) download
copy 
  1.     #include <iostream>
  2.     #include <cstdio>
  3.     #include <algorithm>
  4.     #include <map>
  5.     #define lli long long int
  6.     #define s(x) scanf("%lld", &x)
  7.     using namespace std;
  8.     std::map<lli, lli> prsnt;
  9.     std::map<lli, lli> itachi;
  10.     lli solve(lli j)
  11.     {
  12.     //cout << " called for " << j << " ";
  13.     if ((itachi.find(j) != itachi.end()) &&(itachi[j] == 0))
  14.     return 0;
  15.     if (j == 0) {
  16.     //cout <<"zerro " <<endl;
  17.     return 1;
  18.     }
  19.     else if ((prsnt.find(j) != prsnt.end()) && (prsnt[j] > 0)) {
  20.     --prsnt[j];
  21.     // cout << " yo " << endl;
  22.     return 1;
  23.     } else {
  24.     // cout << " hi " << " " <<endl;
  25.     lli k,i,ans,a1,a2;
  26.     std::map<lli,lli>::iterator iiit;
  27.     for (iiit = prsnt.begin(); ((iiit->first <= j/2) && (iiit != prsnt.end())); ++iiit) {
  28.     if (iiit->second > 0) {
  29.     k = iiit->first;
  30.     --iiit->second;
  31.     a2 = solve(j-k);
  32.     // cout << a2 << endl;
  33.     if (a2) {
  34.     return 1;
  35.     } else {
  36.     ++iiit->second;
  37.     if (itachi.find(iiit->first) != itachi.end()) {
  38.     itachi[iiit->first] = 1;
  39.     }
  40.     }
  41.     }
  42.     }
  43.     itachi[j] = 0;
  44.     return 0;
  45.     }
  46.     }
  47.     int main() {
  48.     // your code goes here
  49.     lli dar,mm,avg,sum,tcase,n,i,j,k,a,b,c,ans,pos,temp;
  50.     s(tcase);
  51.     while (tcase--) {
  52.     prsnt.clear();
  53.     itachi.clear();
  54.     s(n);
  55.     s(temp);
  56.     sum = 0;
  57.     for (i = 0; i < n; ++i) {
  58.     s(j);
  59.     if (i == 0)
  60.     mm = j;
  61.     if (j > 0) {
  62.     if (prsnt.find(j) == prsnt.end()) {
  63.     prsnt[j] = 1;
  64.     }
  65.     else {
  66.     ++prsnt[j];
  67.     }
  68.     sum = sum + j;
  69.     }
  70.     if (j > mm)
  71.     mm = j;
  72.     }
  73.     if (sum % temp != 0) {
  74.     printf("no\n");
  75.     continue;
  76.     } else {
  77.     avg = sum/temp;
  78.     if (avg < mm) {
  79.     printf("no\n");
  80.     continue;
  81.     }
  82.     dar = 0;
  83.     std::map<lli,lli>::reverse_iterator it,jt;
  84.     for (it=prsnt.rbegin(); it!=prsnt.rend(); ++it) {
  85.     while (it->second > 0) {
  86.     --it->second;
  87.     i = solve(avg - it->first);
  88.     if (i != 1){
  89.     ++dar;
  90.     break;
  91.     }
  92.     }
  93.     if (dar > 0)
  94.     break;
  95.     }
  96.     for (it=prsnt.rbegin(); it!=prsnt.rend(); ++it) {
  97.     while (it->second > 0) {
  98.     --it->second;
  99.     i = solve(avg - it->first);
  100.     if (i != 1){
  101.     ++dar;
  102.     break;
  103.     }
  104.     }
  105.     if (dar > 0)
  106.     break;
  107.     }
  108.     if (dar > 0)
  109.     printf("no\n");
  110.     else
  111.     printf("yes\n");
  112.     }
  113.     }
  114.     return 0;
  115.     }
Success #stdin #stdout 0s 3304KB
comments (?)
stdin
copy 
1
1 2
0
stdout
copy 
yes
https://ideone.com/7mjBOX
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!