oj.uz

Submission #40983

# Submission time Handle Problem Language Result Execution time Memory
40983 2018-02-10T18:51:21 Z Hassoony San (COCI17_san) C++14
120 / 120
 178 ms 9032 KB 
#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

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

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2412 KB Output is correct
2 Correct 9 ms 2412 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 9032 KB Output is correct
2 Correct 34 ms 9032 KB Output is correct