oj.uz

Submission #1071735

# Submission time Handle Problem Language Result Execution time Memory
1071735 2024-08-23T10:38:16 Z VMaksimoski008 San (COCI17_san) C++17
120 / 120
 206 ms 34840 KB 
#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

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

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2900 KB Output is correct
2 Correct 9 ms 668 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9644 KB Output is correct
2 Correct 51 ms 1232 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 34840 KB Output is correct
2 Correct 156 ms 5088 KB Output is correct