Submission #40983

#	Time	Username	Problem	Language	Result	Execution time	Memory
40983		Hassoony	San (COCI17_san)	C++14	120 / 120	178 ms	9032 KiB

san

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef double D;
const ll inf=(1ll<<61);
const int mod=1e9+7;
const int MX=20;
const int SQ=350;
int n,m;
ll k;
pair<ll,ll>a[50];
vector<ll>v1[50];
vector<pair<ll,ll> >v;
void calc1(int x,ll sum,int fin,int height){
    if(x==fin){
        if(height)
        v.push_back({height,sum});
        return;
    }
    calc1(x+1,sum,fin,height);
    if(a[x].first>=height)calc1(x+1,sum+a[x].second,fin,a[x].first);
}
void calc2(int x,ll sum,int fin,int height,int ind){
    if(x==fin){
        v1[ind].push_back(sum);
        return;
    }
    calc2(x+1,sum,fin,height,ind);
    if(a[x].first>=height)calc2(x+1,sum+a[x].second,fin,a[x].first,ind);
}
int main(){
    scanf("%d%lld",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%lld%lld",&a[i].first,&a[i].second);
    }
    calc1(0,0,n/2,0);
    for(int i=n/2;i<n;i++){
        calc2(i+1,a[i].second,n,a[i].first,i);
    }
    ll ans=0;
    for(int i=n/2;i<n;i++){
        sort(v1[i].begin(),v1[i].end());
        for(auto pp:v1[i]){
            if(pp>=k)ans++;
        }
    }
    for(auto pp:v){
        ll h=pp.first,money=pp.second;
        if(money>=k)ans++;
        for(int i=n/2;i<n;i++){
            if(a[i].first>=h){
                if(lower_bound(v1[i].begin(),v1[i].end(),k-money)==v1[i].end())continue;
                ans+=v1[i].size()-(lower_bound(v1[i].begin(),v1[i].end(),k-money)-v1[i].begin());
            }
        }
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:33:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld",&n,&k);
                          ^
san.cpp:35:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&a[i].first,&a[i].second);
                                                   ^

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