Submission #52194

#	Time	Username	Problem	Language	Result	Execution time	Memory
52194		EntityIT	San (COCI17_san)	C++14	120 / 120	739 ms	6784 KiB

san

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n, h[2][25], g[2][25], m[2], K;
int ans;
vector<int> th, vec[2][45];

void sieve(int id) {
    for (int mask = 1; mask < (1 << m[id]); ++mask) {
        vector<int> x; x.clear();
        int c = 0;
        for (int i = 0; i < m[id]; ++i) {
            if ( (mask >> i) & 1 ) x.push_back(h[id][i]), c += g[id][i];
        }
        bool ok = 1;
        for (int i = 0; i < x.size() - 1; ++i) {
            if (x[i] > x[i + 1]) { ok = 0; break; }
        }
        if (!ok) continue;
        int _h = (id ? x[0] : x.back() );
        vec[id][(lower_bound(th.begin(), th.end(), _h) - th.begin() )].push_back(c);
        if (c >= K) ans++;
    }
}

signed main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> K;
    m[0] = n / 2; m[1] = n- m[0];
    for (int i = 0; i < n; ++i) {
        int _h, _g; cin >> _h >> _g;
        if (i < m[0]) {
            h[0][i] = _h; g[0][i] = _g;
        }
        else {
            h[1][i - m[0] ] = _h; g[1][i - m[0] ] = _g;
        }
        th.push_back(_h);
    }
    sort (th.begin(), th.end());
    th.erase (unique (th.begin(), th.end() ), th.end() );

    sieve(0); sieve(1);

    for (int i = 0; i < th.size(); ++i) sort (vec[1][i].begin(), vec[1][i].end() );

    for (int i = 0; i < th.size(); ++i) {
        for (int j = i; j < th.size(); ++j) {
            for (int v : vec[0][i]) {
                ans += vec[1][j].end() - lower_bound (vec[1][j].begin(), vec[1][j].end(), K - v);
            }
        }
    }

    cout << ans;

    return  0;
}

Compilation message (stderr)

san.cpp: In function 'void sieve(long long int)':
san.cpp:19:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < x.size() - 1; ++i) {
                         ~~^~~~~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < th.size(); ++i) sort (vec[1][i].begin(), vec[1][i].end() );
                     ~~^~~~~~~~~~~
san.cpp:50:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < th.size(); ++i) {
                     ~~^~~~~~~~~~~
san.cpp:51:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i; j < th.size(); ++j) {
                         ~~^~~~~~~~~~~

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