oj.uz

Submission #170993

# Submission time Handle Problem Language Result Execution time Memory
170993 2019-12-27T00:27:40 Z bloopie Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 299 ms 20880 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2040 KB Output is correct
2 Correct 71 ms 5480 KB Output is correct
3 Correct 290 ms 20824 KB Output is correct
4 Correct 69 ms 5480 KB Output is correct
5 Correct 11 ms 1652 KB Output is correct
6 Correct 8 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2948 KB Output is correct
2 Correct 26 ms 2036 KB Output is correct
3 Correct 111 ms 10592 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 936 KB Output is correct
6 Correct 16 ms 1624 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3564 KB Output is correct
2 Correct 107 ms 6668 KB Output is correct
3 Correct 107 ms 6732 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 58 ms 6628 KB Output is correct
6 Correct 246 ms 20804 KB Output is correct
7 Correct 2 ms 380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 12836 KB Output is correct
2 Correct 26 ms 2036 KB Output is correct
3 Correct 9 ms 1020 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 1016 KB Output is correct
6 Correct 226 ms 12760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2032 KB Output is correct
2 Correct 70 ms 5480 KB Output is correct
3 Correct 9 ms 1016 KB Output is correct
4 Correct 9 ms 1016 KB Output is correct
5 Correct 67 ms 6628 KB Output is correct
6 Correct 25 ms 2032 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 20820 KB Output is correct
2 Correct 27 ms 2032 KB Output is correct
3 Correct 9 ms 1016 KB Output is correct
4 Correct 298 ms 20880 KB Output is correct
5 Correct 77 ms 10592 KB Output is correct
6 Correct 16 ms 1652 KB Output is correct
7 Correct 2 ms 376 KB Output is correct