Submission #1071735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071735		VMaksimoski008	San (COCI17_san)	C++17	120 / 120	206 ms	34840 KiB

san

#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

signed main() {
    ll n, T, ans = 0;
    cin >> n >> T;

    vector<ll> h(n), g(n); set<ll> s;
    for(int i=0; i<n; i++) cin >> h[i] >> g[i], s.insert(h[i]);
    vector<ll> comp(s.begin(), s.end());

    for(auto &x : h) x = lower_bound(comp.begin(), comp.end(), x) - comp.begin();

    auto meet = [&](int l, int r) {
        vector<array<ll, 3> > res;
        int len = r - l + 1;

        for(int s=1; s<(1<<len); s++) {
            ll sum = 0;
            int first = -1, last = -1, ok = 1;

            for(int i=0; i<len; i++) {
                if(s & (1 << i)) {
                    sum += g[l+i];
                    if(last > -1 && h[last] > h[l+i]) ok = 0;
                    if(first == -1) first = l + i;
                    last = l + i;
                }
            }

            if(ok) {
                if(sum >= T) ans++;
                res.push_back({ sum, first, last });
            }
        }

        return res;
    };

    vector<array<ll, 3> > L = meet(0, n/2-1);
    vector<array<ll, 3> > R = meet(n/2, n-1);
    sort(L.begin(), L.end());
    sort(R.rbegin(), R.rend());

    vector<ll> cnt(n);
    int p=-1;
    for(auto &[sum, _, rp] : L) {
        while(p + 1 < R.size() && sum + R[p+1][0] >= T) p++, cnt[h[R[p][1]]]++;
        for(int i=h[rp]; i<n; i++) ans += cnt[i];
    }

    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

san.cpp: In function 'int main()':
san.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         while(p + 1 < R.size() && sum + R[p+1][0] >= T) p++, cnt[h[R[p][1]]]++;
      |               ~~~~~~^~~~~~~~~~

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