Submission #44949

#	Time	Username	Problem	Language	Result	Execution time	Memory
44949		bogdan10bos	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	240 ms	21596 KiB

bobek

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;
int N;
int lg2[1100005];
LL V, v[45];
LL sum[2][1100005];

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d", &N);
    scanf("%lld", &V);
    for(int i = 0; i < N; i++) scanf("%lld", &v[i]);
    for(int i = N; i <= 39; i++)    v[i] = LL(1e18 + 1);

    int mxmsk = (1 << 20) - 1;
    for(int i = 2; i <= mxmsk; i++)
    {
        lg2[i] = lg2[i - 1];
        if( (2 << lg2[i]) == i )    lg2[i]++;
    }

    for(int i = 0; i <= 1; i++)
    {
        int pos = i * 20;
        for(int msk = 1; msk <= mxmsk; msk++)
        {
            int b = lg2[msk];
            sum[i][msk] = min(LL(1e18 + 1), sum[i][msk ^ (1 << b)] + v[b + pos] );
        }
        sort(sum[i], sum[i] + mxmsk + 1);
    }

    int pos = mxmsk;
    LL ans = 0LL;
    for(int i = 0; i <= mxmsk; i++)
    {
        if(sum[0][i] > V)   break;
        while(V - sum[1][pos] < sum[0][i])
            pos--;
        ans += (pos + 1);
    }
    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
bobek.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &V);
     ~~~~~^~~~~~~~~~~~
bobek.cpp:22:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < N; i++) scanf("%lld", &v[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