oj.uz

Submission #40213

# Submission time Handle Problem Language Result Execution time Memory
40213 2018-01-29T19:10:08 Z evpipis San (COCI17_san) C++
120 / 120
 653 ms 52664 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
typedef long long ll;

pair<ll, ll> a[25], b[25];
vector<ll> vec[25];

int main(){
    int n, m;
    ll k;
    scanf("%d %lld", &n, &k);
    m = n-n/2;
    n = n/2;
    for (int i = 0; i < n; i++)
        scanf("%lld %lld", &a[i].fi, &a[i].se);
    for (int i = 0; i < m; i++)
        scanf("%lld %lld", &b[i].fi, &b[i].se);

    ll ans = 0;
    for (int bit = 0; bit < (1<<n); bit++){
        ll cur = 0;
        int pos = -1, can = 1;
        for (int i = 0; i < n; i++)
            if (bit & (1<<i)){
                if (pos != -1 && a[pos].fi > a[i].fi){
                    can = 0;
                    break;
                }
                pos = i;
                cur += a[i].se;
            }

        for (int i = 0; i < m && pos != -1 && can; i++)
            if (a[pos].fi <= b[i].fi)
                vec[i].pb(cur);

        if (pos == -1)
            for (int i = 0; i < m; i++)
                vec[i].pb(0LL);

        if (cur >= k && can) ans++;
    }

    for (int i = 0; i < m; i++)
        sort(vec[i].begin(), vec[i].end());

    //printf("%d %d\n", vec[0].size(), vec[1].size());

    for (int bit = 1; bit < (1<<m); bit++){
        ll cur = 0;
        int pos = -1, can = 1, fir = -1;
        for (int i = 0; i < m; i++)
            if (bit & (1<<i)){
                //printf("now %d is on\n", i);
                if (pos != -1 && b[pos].fi > b[i].fi){
                    can = 0;
                    break;
                }
                pos = i;
                if (fir == -1) fir = i;
                cur += b[i].se;
            }

        //printf("cur == %lld\n", cur);
        if (can)
            ans += vec[fir].end()-lower_bound(vec[fir].begin(), vec[fir].end(), k-cur);
    }

    printf("%lld\n", ans);
    return 0;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:15:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld", &n, &k);
                             ^
san.cpp:19:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &a[i].fi, &a[i].se);
                                               ^
san.cpp:21:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &b[i].fi, &b[i].se);
                                               ^

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6520 KB Output is correct
2 Correct 5 ms 2296 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12156 KB Output is correct
2 Correct 39 ms 6340 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 52664 KB Output is correct
2 Correct 209 ms 19092 KB Output is correct