oj.uz

Submission #146699

# Submission time Handle Problem Language Result Execution time Memory
146699 2019-08-25T09:47:51 Z BartolM San (COCI17_san) C++17
120 / 120
 147 ms 10704 KB 
#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

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

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2664 KB Output is correct
2 Correct 6 ms 1012 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 10704 KB Output is correct
2 Correct 24 ms 2536 KB Output is correct