Submission #416676

#	Time	Username	Problem	Language	Result	Execution time	Memory
416676		fadi57	San (COCI17_san)	C++14	0 / 120	583 ms	26996 KiB

san

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;

const int mx=50;
typedef long long ll;
int inf=1e9+10;
const int mod=1e9+7;
int n,m,k,p,l,q;

int h[mx];
int g[mx];


typedef tree< pair < long long, int >, null_type, less<pair < long long, int >>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 ordered_set s;
int main(){

    cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>h[i]>>g[i];
      }
      int mid=(n+1)/2;
      vector<pair<int,int>>v;
      for(int i=0;i<(1<<mid);i++){
        ll sum=0;
        int last=0;
        int ok=1;
        for(int j=0;j<mid;j++){

            if(i&(1<<j)){
                if(h[j]>last){
                    last=h[j];
                    sum+=g[j];
                }else{
            ok=0;
            break;
             }
            }
        }
        if(ok){

            v.push_back({last,sum});
        }

      }
      sort(v.begin(),v.end());
    vector<pair<int,pair<int,int>>>vv;
    int z=n-mid;
    for(int i=0;i<(1<<z);i++){
            int ok=1;
        int first=inf;
        int last=0;
        int sum=0;
        for(int j=0;j<z;j++){
                if(i&(1<<j)){

                       if(first==inf){
                    first=h[j+mid];
                    last=h[j+mid];


                }else{
                if(h[j+mid]<=last){
                    ok=0;break;

                }


                }
                last=h[j+mid];
                sum+=g[j+mid];
                }




        }
        if(ok){

            vv.push_back({first,{sum,i}});
            s.insert({sum,i});

        }

    }
    sort(vv.begin(),vv.end());
    int j=0;  int si=vv.size();
    ll ans=0;
    for(auto it:v){
      //cout<<it.first<<" "<<it.second<<" ";
       while(j<si&&vv[j].first<it.first){
            s.erase(vv[j].second);
            j++;

       }
         ans += ((int)s.size() - (int)s.order_of_key({max(k - it.second, 0), 0}));

    }

   cout<<ans;
  }

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