Submission #1113856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113856		vjudge1	San (COCI17_san)	C++17	120 / 120	201 ms	10684 KiB

san

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long n,k;
    cin>>n>>k;
    vector<pair<long long,long long>> vec;
    for(long long n1=n;n1>0;n1--)
    {
        long long a,b;
        cin>>a>>b;
        vec.push_back({a,b});
    }
    long long right=n/2;
    long long res=0;
    vector<pair<long long,long long>> l;
    for(long long i=0;i<pow(2,right);i++)
    {
        long long br=i;
        long long lastval=-1,last=-1,sum=0;
        bool pos=true;
        for(long long j=0;br>0;br=br>>1,j++)
        {
            if(br&1==1)
            {
                if(vec[j].first<lastval)
                {
                    pos=false;
                    break;
                }
                else
                {
                    lastval=vec[j].first;
                    last=j;
                    sum+=vec[j].second;
                }

            }
        }
        if(pos==true)
        {
            if(last!=-1)
            l.push_back({sum,lastval});
        }
    }
    vector<long long> r[41];
    for(long long i=0;i<pow(2,n-right);i++)
    {

        long long br=i;
        long long lastval=-1,first=-1,sum=0;
        bool pos=true;

        for(long long j=0;br>0;br=br>>1,j++)
        {

            if(br&1==1)
            {
                if(vec[j+right].first<lastval)
                {
                    pos=false;
                    break;
                }
                else
                {
                    lastval=vec[j+right].first;
                    if(first==-1)
                        first=j+right;
                    sum+=vec[j+right].second;
                }

            }
        }

        if(pos==true)
        {
            if(first!=-1)
            {
            r[first].push_back(sum);
                if(sum>=k)
                    res++;
            }
        }
    }

    for(long long i=0;i<=40;i++)
    {
        sort(r[i].begin(),r[i].end());
    }
    for(auto it : l)
    {
        if(it.first>=k)
            res++;
        for(long long i=0;i<=40;i++)
        {

                if(vec[i].first>=it.second)
                {
                    long long br=it.first;
                    long long l=0,rr=r[i].size()-1;
                    long long m=(l+rr)/2;
                    for(;l<=rr;m=(l+rr)/2)
                    {
                        if(r[i][m]+br<k)
                        {
                            l=m+1;
                        }
                        else
                            rr=m-1;
                    }
                    res+=r[i].size()-l;
                }

        }
    }
    cout<<res;
    return 0;
}

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:26:20: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   26 |             if(br&1==1)
      |                   ~^~~
san.cpp:59:20: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   59 |             if(br&1==1)
      |                   ~^~~

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24