Submission #534750

#	Time	Username	Problem	Language	Result	Execution time	Memory
534750		cig32	San (COCI17_san)	C++17	120 / 120	164 ms	46412 KiB

san

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) { 
  if(p==0) return 1;
  int r = bm(b, p/2);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) {
  return bm(b, MOD-2);
}
int f[MAXN];
int nCr(int n, int r) { 
  int ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}

void precomp() { 
  f[0] = 1;
  for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
}

void solve(int tc) {
  int n, k;
  cin >> n >> k;
  int h[n], g[n];
  for(int i=0; i<n; i++) {
    cin >> h[i] >> g[i];
  }
  if(n == 1) {
    cout << (g[0] >= k ? 1 : 0) << "\n";
    return;
  }
  vector<int> l[n/2];
  vector<pair<int, int> > oof;
  int s = n/2;
  int ans = 0;
  for(int i=0; i<(1<<s); i++) {
    bool valid = 1;
    int sum = 0;
    int prv = -1;
    int last_id = -1;
    for(int j=0; j<s; j++) {
      if(i & (1<<j)) {
        if(h[j] < prv) valid = 0;
        prv = h[j];
        sum += g[j];
        last_id = j;
      }
    }
    if(valid) oof.push_back({sum, last_id});
  }
  sort(oof.begin(), oof.end());
  reverse(oof.begin(), oof.end());
  int t = oof.size();
  int ps[t][s];
  for(int i=0; i<t; i++) {
    for(int j=0; j<s; j++) {
      ps[i][j] = 0;
    }
  }
  for(int i=0; i<t; i++) {
    for(int j=0; j<s; j++) {
      ps[i][j] = (i == 0 ? 0 : ps[i-1][j]) + (oof[i].second == j);
    }
  }
  int og = s;
  s = n - s;
  for(int i=0; i<(1<<s); i++) {
    bool valid = 1;
    int sum = 0;
    int prv = -1;
    int first_id = -1;
    for(int j=0; j<s; j++) {
      if(i & (1<<j)) {
        if(h[j + og] < prv) valid = 0;
        prv = h[j + og];
        sum += g[j + og];
        first_id = (first_id == -1 ? j + og : first_id);
      }
    }
    if(!valid) continue;
    int lb = 0, rb = t - 1;
    while(lb < rb) {
      int mid = (lb + rb + 1) >> 1;
      if(oof[mid].first + sum >= k) lb = mid;
      else rb = mid - 1;
    }
    if(sum >= k) {
      ans++;
    }
    if(oof[lb].first + sum >= k) {
      //cout << "msk = " << i << ", first id = " << first_id << "\n";
      int wg = ans;
      for(int j=0; j<og; j++) {
        if(first_id == -1 || h[j] <= h[first_id]) {
          ans += ps[lb][j];
        }
      }
      //cout << "ans increment: " << ans - wg << "\n";
    }
  }
  cout << ans << "\n";
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

Compilation message (stderr)

san.cpp: In function 'void solve(long long int)':
san.cpp:101:11: warning: unused variable 'wg' [-Wunused-variable]
  101 |       int wg = ans;
      |           ^~

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