Submission #40213

#	Time	Username	Problem	Language	Result	Execution time	Memory
40213		evpipis	San (COCI17_san)	C++98	120 / 120	653 ms	52664 KiB

san

#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 (stderr)

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 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24