Submission #146699

#	Time	Username	Problem	Language	Result	Execution time	Memory
146699		BartolM	San (COCI17_san)	C++17	120 / 120	147 ms	10704 KiB

san

#include <bits/stdc++.h>
using namespace std;

vector < pair<long long, long long> > V;
vector <long long> saz;
vector < pair<long long, long long> > Lijevo;
vector<long long> Desno[45];
long long n,k,u,h,g;
long long koliko=0;

int RekLijevo(long long K,long long B,long long i)
{
//    printf("K: %lld B: %d i %d\n", K, B, i);
    if (n/2==i) {
        if (K==0) return 0;
        if (K>=k) koliko++;
        Lijevo.push_back({B,K});
        return 1;
    }
    RekLijevo(K,B,i+1);
    if (V[i].first>=B)
        RekLijevo(K+V[i].second,V[i].first,i+1);
}

int RekDesno(long long K,long long B,long long i,long long P)
{
    if (n==i) {
        if (K==0) return 0;
        if (K>=k) koliko++;
        Desno[B].push_back(K);
        return 1;
    }
    RekDesno(K,B,i+1,P);
    if (V[i].first>=P)
        RekDesno(K+V[i].second,min(B, V[i].first),i+1,V[i].first);
}

int main()
{
    cin >> n >> k;
    for (int i=0;i<n;i++){
        cin >> u >> h;
        V.push_back({u,h});
        saz.push_back(u);
    }

    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());
    for (int i=0;i<n;i++){
        V[i].first=lower_bound(saz.begin(), saz.end(), V[i].first)-saz.begin();
    }

    RekLijevo(0,0,0);
    RekDesno(0,999999,n/2,0);

    for (int i=0;i<40;i++){
            sort(Desno[i].begin(), Desno[i].end());
    }


    long long lo;

    for (int i=0;i<Lijevo.size();i++){
        h=Lijevo[i].first;
        g=Lijevo[i].second;
        for (int j=h;j<40;j++){
            if (Desno[j].size()==0) continue;
            if (Desno[j].back()<(k-g)) continue;
            lo=lower_bound(Desno[j].begin(), Desno[j].end(), (k-g))-Desno[j].begin();
            koliko+=max((int)Desno[j].size()-lo, 0LL);
        }
    }
    cout << koliko;
}

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<Lijevo.size();i++){
                  ~^~~~~~~~~~~~~~
san.cpp: In function 'int RekLijevo(long long int, long long int, long long int)':
san.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
san.cpp: In function 'int RekDesno(long long int, long long int, long long int, long long int)':
san.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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