oj.uz

Submission #1113856

# Submission time Handle Problem Language Result Execution time Memory
1113856 2024-11-17T15:36:21 Z vjudge1 San (COCI17_san) C++17
120 / 120
 201 ms 10684 KB 
#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

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

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1396 KB Output is correct
2 Correct 5 ms 336 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2100 KB Output is correct
2 Correct 24 ms 972 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 10684 KB Output is correct
2 Correct 123 ms 3524 KB Output is correct