oj.uz

Submission #44949

# Submission time Handle Problem Language Result Execution time Memory
44949 2018-04-09T20:05:21 Z bogdan10bos Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 240 ms 21596 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20984 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20984 KB Output is correct
2 Correct 55 ms 20984 KB Output is correct
3 Correct 58 ms 21100 KB Output is correct
4 Correct 56 ms 21136 KB Output is correct
5 Correct 59 ms 21136 KB Output is correct
6 Correct 56 ms 21136 KB Output is correct
7 Correct 56 ms 21136 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 21136 KB Output is correct
2 Correct 60 ms 21144 KB Output is correct
3 Correct 67 ms 21148 KB Output is correct
4 Correct 56 ms 21152 KB Output is correct
5 Correct 58 ms 21204 KB Output is correct
6 Correct 142 ms 21268 KB Output is correct
7 Correct 68 ms 21288 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 21288 KB Output is correct
2 Correct 82 ms 21288 KB Output is correct
3 Correct 62 ms 21288 KB Output is correct
4 Correct 61 ms 21288 KB Output is correct
5 Correct 88 ms 21356 KB Output is correct
6 Correct 65 ms 21420 KB Output is correct
7 Correct 65 ms 21420 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 21420 KB Output is correct
2 Correct 143 ms 21420 KB Output is correct
3 Correct 240 ms 21444 KB Output is correct
4 Correct 142 ms 21444 KB Output is correct
5 Correct 91 ms 21444 KB Output is correct
6 Correct 118 ms 21444 KB Output is correct
7 Correct 139 ms 21444 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 21444 KB Output is correct
2 Correct 136 ms 21444 KB Output is correct
3 Correct 127 ms 21444 KB Output is correct
4 Correct 56 ms 21444 KB Output is correct
5 Correct 79 ms 21444 KB Output is correct
6 Correct 127 ms 21444 KB Output is correct
7 Correct 143 ms 21484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 21484 KB Output is correct
2 Correct 146 ms 21484 KB Output is correct
3 Correct 148 ms 21508 KB Output is correct
4 Correct 74 ms 21508 KB Output is correct
5 Correct 80 ms 21508 KB Output is correct
6 Correct 180 ms 21508 KB Output is correct
7 Correct 149 ms 21508 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 21508 KB Output is correct
2 Correct 139 ms 21508 KB Output is correct
3 Correct 142 ms 21508 KB Output is correct
4 Correct 62 ms 21508 KB Output is correct
5 Correct 87 ms 21508 KB Output is correct
6 Correct 183 ms 21536 KB Output is correct
7 Correct 141 ms 21536 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 21536 KB Output is correct
2 Correct 145 ms 21536 KB Output is correct
3 Correct 140 ms 21536 KB Output is correct
4 Correct 141 ms 21556 KB Output is correct
5 Correct 92 ms 21564 KB Output is correct
6 Correct 154 ms 21564 KB Output is correct
7 Correct 229 ms 21564 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 21564 KB Output is correct
2 Correct 144 ms 21580 KB Output is correct
3 Correct 141 ms 21580 KB Output is correct
4 Correct 236 ms 21580 KB Output is correct
5 Correct 89 ms 21580 KB Output is correct
6 Correct 139 ms 21596 KB Output is correct
7 Correct 137 ms 21596 KB Output is correct