oj.uz

Submission #184112

# Submission time Handle Problem Language Result Execution time Memory
184112 2020-01-10T20:50:52 Z nicolaalexandra Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 536 ms 8580 KB 
#include <bits/stdc++.h>
#define DIMN 50
#define DIMM 2000000
using namespace std;
long long v[DIMN],d[DIMM];
long long m;
int n,i,k;
int main (){

    cin>>n>>m;
    for (i=1;i<=n;i++)
        cin>>v[i];

    /// iau toate mastile din prima jumatate
    int val = n/2;
    for (long long mask=0;mask<(1<<val);mask++){
        long long sum = 0;
        for (int bit=0;bit<val;bit++)
            if (mask&(1<<bit))
                sum += v[bit+1];
        if (sum <= m)
            d[++k] = sum;
    }
    sort (d+1,d+k+1);
    val = n - n/2;
    long long ans = 0;
    for (long long mask=0;mask<(1<<val);mask++){
        long long sum = 0;
        for (int bit=0;bit<val;bit++)
            if (mask&(1<<bit))
                sum += v[n/2+bit+1];
        if (sum > m)
            continue;
        long long dif = m - sum;
        int st = 1, dr = k, sol = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (d[mid] <= dif){
                sol = mid;
                st = mid+1;
            } else dr = mid-1;
        }
        ans += sol;
    }
    cout<<ans;

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 2 ms 404 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 372 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 368 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 352 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 352 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 888 KB Output is correct
2 Correct 121 ms 2416 KB Output is correct
3 Correct 512 ms 8572 KB Output is correct
4 Correct 123 ms 2420 KB Output is correct
5 Correct 18 ms 884 KB Output is correct
6 Correct 10 ms 656 KB Output is correct
7 Correct 12 ms 252 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1392 KB Output is correct
2 Correct 40 ms 880 KB Output is correct
3 Correct 231 ms 4468 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 9 ms 504 KB Output is correct
6 Correct 18 ms 860 KB Output is correct
7 Correct 11 ms 400 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1392 KB Output is correct
2 Correct 201 ms 2424 KB Output is correct
3 Correct 173 ms 2412 KB Output is correct
4 Correct 2 ms 368 KB Output is correct
5 Correct 102 ms 2424 KB Output is correct
6 Correct 288 ms 8576 KB Output is correct
7 Correct 64 ms 372 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 4464 KB Output is correct
2 Correct 34 ms 860 KB Output is correct
3 Correct 12 ms 504 KB Output is correct
4 Correct 2 ms 360 KB Output is correct
5 Correct 10 ms 616 KB Output is correct
6 Correct 212 ms 4468 KB Output is correct
7 Correct 11 ms 372 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 876 KB Output is correct
2 Correct 116 ms 2412 KB Output is correct
3 Correct 11 ms 616 KB Output is correct
4 Correct 12 ms 620 KB Output is correct
5 Correct 127 ms 2388 KB Output is correct
6 Correct 25 ms 876 KB Output is correct
7 Correct 172 ms 364 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 8576 KB Output is correct
2 Correct 41 ms 888 KB Output is correct
3 Correct 13 ms 624 KB Output is correct
4 Correct 536 ms 8580 KB Output is correct
5 Correct 151 ms 4468 KB Output is correct
6 Correct 18 ms 876 KB Output is correct
7 Correct 22 ms 348 KB Output is correct