oj.uz

답안 #161817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161817 2019-11-04T13:53:43 Z dantoh000 Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 456 ms 8700 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    ll m;
    scanf("%d%lld",&n,&m);
    ll a[n];
    for (int i = 0; i < n; i++) scanf("%lld",&a[i]);
    int ct = 0;
    int k = min(20,n-1);
    vector<ll> v(1<<k);
    for (int i = 0; i < (1<<k); i++){
        int cur = i;
        ll sum = 0;
        while (cur){
            int lsb = (cur)&(-cur);
            sum += a[__builtin_ctz(lsb)];
            cur -= lsb;
        }
        v[i] = sum;
    }
    sort(v.begin(),v.end());
    ll ans = 0;
    for (int i = 0; i < (1<<(n-k)); i++){
        int cur = i;
        ll sum = 0;
        while (cur){
            int lsb = (cur)&(-cur);
            sum += a[__builtin_ctz(lsb)+k];
            cur -= lsb;
        }
        //printf("%d %lld %lld\n",i,sum,(ll)(upper_bound(v.begin(),v.end(),m-sum)-v.begin()));
        ans += upper_bound(v.begin(),v.end(),m-sum)-v.begin();
    }
    printf("%lld\n",ans);
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:10:9: warning: unused variable 'ct' [-Wunused-variable]
     int ct = 0;
         ^~
bobek.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~
bobek.cpp:9:38: 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",&a[i]);
                                 ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 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 364 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 4 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 61 ms 4636 KB Output is correct
7 Correct 8 ms 888 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 4512 KB Output is correct
2 Correct 15 ms 1400 KB Output is correct
3 Correct 5 ms 616 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 38 ms 4472 KB Output is correct
6 Correct 8 ms 888 KB Output is correct
7 Correct 8 ms 888 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 8584 KB Output is correct
2 Correct 144 ms 8568 KB Output is correct
3 Correct 455 ms 8568 KB Output is correct
4 Correct 141 ms 8696 KB Output is correct
5 Correct 78 ms 8588 KB Output is correct
6 Correct 98 ms 8568 KB Output is correct
7 Correct 122 ms 8568 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 8616 KB Output is correct
2 Correct 121 ms 8580 KB Output is correct
3 Correct 174 ms 8696 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 63 ms 8568 KB Output is correct
6 Correct 134 ms 8580 KB Output is correct
7 Correct 124 ms 8596 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 8568 KB Output is correct
2 Correct 201 ms 8592 KB Output is correct
3 Correct 160 ms 8568 KB Output is correct
4 Correct 16 ms 1400 KB Output is correct
5 Correct 77 ms 8580 KB Output is correct
6 Correct 166 ms 8696 KB Output is correct
7 Correct 133 ms 8700 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 8588 KB Output is correct
2 Correct 126 ms 8568 KB Output is correct
3 Correct 128 ms 8568 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 70 ms 8568 KB Output is correct
6 Correct 158 ms 8700 KB Output is correct
7 Correct 131 ms 8568 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 8568 KB Output is correct
2 Correct 145 ms 8584 KB Output is correct
3 Correct 124 ms 8568 KB Output is correct
4 Correct 127 ms 8616 KB Output is correct
5 Correct 96 ms 8588 KB Output is correct
6 Correct 123 ms 8568 KB Output is correct
7 Correct 164 ms 8568 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 359 ms 8592 KB Output is correct
2 Correct 126 ms 8568 KB Output is correct
3 Correct 126 ms 8696 KB Output is correct
4 Correct 456 ms 8568 KB Output is correct
5 Correct 99 ms 8568 KB Output is correct
6 Correct 126 ms 8568 KB Output is correct
7 Correct 124 ms 8584 KB Output is correct