oj.uz

Submission #52194

# Submission time Handle Problem Language Result Execution time Memory
52194 2018-06-24T16:07:23 Z EntityIT San (COCI17_san) C++14
120 / 120
 739 ms 6784 KB 
#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

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

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 480 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1264 KB Output is correct
2 Correct 46 ms 1264 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 2012 KB Output is correct
2 Correct 307 ms 2012 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 6784 KB Output is correct
2 Correct 739 ms 6784 KB Output is correct