Submission #66245

#	Time	Username	Problem	Language	Result	Execution time	Memory
66245		Flying_dragon_02	San (COCI17_san)	C++14	120 / 120	204 ms	7968 KiB

san

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

int n;
long long h[45], g[45], lol;
long long amount = 0;
vector<long long> graph[2][45], data;

void backtrack(int pos, int limit, long long height, long long sum, long long dist){
    if(pos == limit + 1){
        if(sum == 0) return ;
        //cout << sum << "\n";
        if(limit == n / 2){
            int it = lower_bound(data.begin(), data.end(), height) - data.begin();
            graph[0][it].pb(sum);
        }
        else{
            int it = lower_bound(data.begin(), data.end(), dist) - data.begin();
            graph[1][it].pb(sum);
        }
        return ;
    }
    backtrack(pos + 1, limit, height, sum, dist);
    if(h[pos] >= height){
        if(dist == -1 && limit == n)
            backtrack(pos + 1, limit, h[pos], sum + g[pos], h[pos]);
        else if(limit == n)
            backtrack(pos + 1, limit, h[pos], sum + g[pos], dist);
        else if(limit == n / 2)
            backtrack(pos + 1, limit, h[pos], sum + g[pos], dist);
    }
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> lol;
    for(int i = 1; i <= n; i++){
        cin >> h[i] >> g[i];
        data.pb(h[i]);
    }
    sort(data.begin(), data.end());
    data.erase(unique(data.begin(),data.end()),data.end());
    backtrack(1, n / 2, -1, 0, -1);
    backtrack(n / 2 + 1, n, -1, 0, -1);
    for(int i = 0; i < data.size(); i++){
        for(int j = 0; j < 2; j++){
            for(int l = 0; l < graph[j][i].size(); l++){
                if(graph[j][i][l] >= lol)
                    amount++;
            }
            sort(graph[j][i].begin(), graph[j][i].end());
        }
    }
    //cout << amount << "\n";
    for(int i = 0; i < data.size(); i++){
        for(int j = 0; j < graph[0][i].size(); j++){
            for(int k = i; k < data.size(); k++){
                //cout << data[i] << " " << data[k] << " " << graph[0][i].size() << " " << graph[1][k].size() << "\n";
                if(graph[1][k].size() == 0) continue;
                //if(graph[0][i][j] >= k) {amount += graph[1][k].size(); continue;}
                int l = 0, r = graph[1][k].size() - 1, mid;
                while(l < r){
                    mid = (l + r) / 2;
                    if(graph[0][i][j] + graph[1][k][mid] >= lol)
                        r = mid;
                    else
                        l = mid + 1;
                }
                if(graph[0][i][j] + graph[1][k][l] >= lol)
                    amount += graph[1][k].size() - l;
            }
        }
    }
    cout << amount << "\n";
}
/*4 15
5 5
5 12
6 10
2 1*/

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < data.size(); i++){
                    ~~^~~~~~~~~~~~~
san.cpp:55:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int l = 0; l < graph[j][i].size(); l++){
                            ~~^~~~~~~~~~~~~~~~~~~~
san.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < data.size(); i++){
                    ~~^~~~~~~~~~~~~
san.cpp:64:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < graph[0][i].size(); j++){
                        ~~^~~~~~~~~~~~~~~~~~~~
san.cpp:65:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k = i; k < data.size(); k++){
                            ~~^~~~~~~~~~~~~

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