oj.uz

Submission #55551

# Submission time Handle Problem Language Result Execution time Memory
55551 2018-07-07T22:09:20 Z zelinski Ice Hockey World Championship (CEOI15_bobek) C++11
100 / 100
 236 ms 17400 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define MaxN 20
#define MaxG 1048576
#define int64 long long
using namespace std;

int64 sum[2][MaxG+1];
int64 v[2][MaxN+1];
int64 x[MaxN+1];
int64 temp,K;
int N,M,X,Y,P;
int C[2];

void Solve(int l, int N)
{
    if(!N) sum[l][ ++C[l] ] = temp;
    else{
        temp = temp + v[l][N];
        Solve(l, N-1);

        temp = temp - v[l][N];
        Solve(l, N-1);
    }
}

int main(){
    /*
    freopen("file.in","r",stdin);
    freopen("file.out","w",stdout);
    */

    int i,j;
    int64 res = 0;

    scanf("%d %lld",&P,&K);
    for(i = 1; i <= P/2; ++i) scanf("%lld",&x[++N]);
    sort(x+1, x+N+1);
    for(i = 1; i <= N; ++i) v[0][i] = x[i];

    for(i = (P+2)/2; i <= P; ++i) scanf("%lld",&x[++M]);
    sort(x+1, x+M+1);
    for(i = 1; i <= M; ++i) v[1][i] = x[i];

    Solve(0, N);
    Solve(1, M);

    X = C[0]; Y = C[1];
    sort(sum[0]+1, sum[0]+X+1);
    sort(sum[1]+1, sum[1]+Y+1);
    for(i = 1, j = Y; i <= X; ++i)
    {
        while(sum[0][i] + sum[1][j] > K && j) --j;
        res = res + j;
    }

    printf("%lld\n",res);


return 0;
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld",&P,&K);
     ~~~~~^~~~~~~~~~~~~~~~~
bobek.cpp:38:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i = 1; i <= P/2; ++i) scanf("%lld",&x[++N]);
                               ~~~~~^~~~~~~~~~~~~~~~
bobek.cpp:42:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i = (P+2)/2; i <= P; ++i) scanf("%lld",&x[++M]);
                                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
6 Correct 3 ms 516 KB Output is correct
7 Correct 2 ms 608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 644 KB Output is correct
2 Correct 2 ms 688 KB Output is correct
3 Correct 3 ms 688 KB Output is correct
4 Correct 2 ms 692 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 2 ms 860 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2304 KB Output is correct
2 Correct 57 ms 4852 KB Output is correct
3 Correct 221 ms 17188 KB Output is correct
4 Correct 58 ms 17188 KB Output is correct
5 Correct 9 ms 17188 KB Output is correct
6 Correct 8 ms 17188 KB Output is correct
7 Correct 14 ms 17188 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 17188 KB Output is correct
2 Correct 20 ms 17188 KB Output is correct
3 Correct 87 ms 17188 KB Output is correct
4 Correct 2 ms 17188 KB Output is correct
5 Correct 5 ms 17188 KB Output is correct
6 Correct 13 ms 17188 KB Output is correct
7 Correct 14 ms 17188 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17188 KB Output is correct
2 Correct 85 ms 17188 KB Output is correct
3 Correct 79 ms 17188 KB Output is correct
4 Correct 3 ms 17188 KB Output is correct
5 Correct 39 ms 17188 KB Output is correct
6 Correct 179 ms 17220 KB Output is correct
7 Correct 77 ms 17220 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 17220 KB Output is correct
2 Correct 19 ms 17220 KB Output is correct
3 Correct 8 ms 17220 KB Output is correct
4 Correct 3 ms 17220 KB Output is correct
5 Correct 6 ms 17220 KB Output is correct
6 Correct 165 ms 17220 KB Output is correct
7 Correct 15 ms 17220 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17220 KB Output is correct
2 Correct 60 ms 17220 KB Output is correct
3 Correct 9 ms 17220 KB Output is correct
4 Correct 9 ms 17220 KB Output is correct
5 Correct 43 ms 17220 KB Output is correct
6 Correct 20 ms 17220 KB Output is correct
7 Correct 218 ms 17260 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 17264 KB Output is correct
2 Correct 21 ms 17264 KB Output is correct
3 Correct 9 ms 17264 KB Output is correct
4 Correct 236 ms 17400 KB Output is correct
5 Correct 54 ms 17400 KB Output is correct
6 Correct 14 ms 17400 KB Output is correct
7 Correct 27 ms 17400 KB Output is correct