Submission #170993

#	Time	Username	Problem	Language	Result	Execution time	Memory
170993		bloopie	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	299 ms	20880 KiB

bobek

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 41;
unordered_map<ll,ll> memo[MAXN];
unordered_map<ll,ll> memo2[MAXN];
int n;
ll mm;
ll a[MAXN];
ll b[MAXN];
int n1,n2;
vector<ll> p1,p2;
void solve1(int i,ll m)
{
    if(m > mm)
       return;
    if(i == n1)
      {
          p1.push_back(m);
          return;
      }
    
   solve1(i + 1 , m);
   solve1(i + 1 , m + a[i]);
}

void solve2(int i,ll m)
{
    if(m > mm)
       return ;
    if(i == n2)
      {
          p2.push_back(m);
          return;
      }
    
   solve2(i + 1 , m);
   solve2(i + 1 , m + b[i]);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> mm;
    n1 = n / 2;
    n2 = n - n / 2;
    for(int i = 0 ; i < n1 ; i++)
       cin >> a[i];
    for(int i = 0 ; i < n2 ; i++)
       cin >> b[i];
    
    solve1(0,0);
    solve2(0,0);
    sort(p1.begin(),p1.end());
    sort(p2.begin(),p2.end());
    ll ans = 0;
    if(p1.size() < p2.size())
     swap(p1,p2);
    for(int i = 0 ; i < p1.size() ; i++)
     {
         //++ans;
         auto idx = upper_bound(p2.begin(),p2.end(),mm - p1[i]) - p2.begin();
         ans+=idx;
     }
     cout << ans ;
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < p1.size() ; i++)
                     ~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10