제출 #146698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146698		BartolM	San (COCI17_san)	C++17	0 / 120	235 ms	10736 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];
int n,k,u,h,g;
long long koliko=0;

int RekLijevo(long long K,int B,int 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,int B,int i,int 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, (int)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;
}

컴파일 시 표준 에러 (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, int, int)':
san.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
san.cpp: In function 'int RekDesno(long long int, int, int, int)':
san.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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