oj.uz

Submission #631214

# Submission time Handle Problem Language Result Execution time Memory
631214 2022-08-17T20:34:11 Z epicci23 San (COCI17_san) C++17
120 / 120
 65 ms 9064 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n" 
#define MOD 1000000007
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
const int N=200005;
const long long INF = LLONG_MAX;
const int INF2=(int)1e18;
const int LOG=20;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//sunlari dusun//
/*
 * kodu kisaltcak  fonksiyon
 * cevaba binary search ya da normal bs
 * segment tree / sparse table
 * stack
 * teklik ciftlik
 * precomputation
 * EN ONEMLISI OVERKILLEME
 * edge case dusunr
 * constraintlere bak
 * indisleri kontrol et 
 * dp
 * greedy
 * sorting
 * dfs bfs
 * sieve
*/



int n,k;
pii arr[45];
vector<int> v[45];
bool vis[(1LL<<22)];
int cnt=0;
void f(int ind,int mask,int last,int sum)
{
  //cout << ind << " " << mask << " " << last << " " << sum << endl;
   if(!vis[mask])
   {
    //cout << "a:" << endl;
     vis[mask]=1;
     if(sum>=k) cnt++;
     for(int i=n/2;i<=n;i++)
     {
        if(last==0 || arr[last].ff<=arr[i].ff)
        {
           if(sum>=k)
           { 
            cnt+=sz(v[i]);
          //  cout << "cnt: "  << cnt << endl;
            }
           else
           {
             int need=k-sum;
             int it=lower_bound(all(v[i]),need)-v[i].begin();
             cnt+=sz(v[i])-it;
           //  cout << "cnt: "  << cnt << endl;
           }
        }
     }

   }
   if(ind==n/2) return;
   if(last==0 || arr[ind].ff>=arr[last].ff) f(ind+1,mask|(1LL<<ind),ind,sum+arr[ind].ss);
   f(ind+1,mask,last,sum);
}


void solve()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> arr[i].ff >> arr[i].ss;
    for(int i=n;i>=n/2;i--)
    {
        v[i].pb(arr[i].ss);
        for(int j=i+1;j<=n;j++)
        {
          if(arr[i].ff <= arr[j].ff)
          {
            for(int x:v[j]) v[i].pb(x+arr[i].ss);
          }
        }
        sort(all(v[i]));
      //  for(int x:v[i]) cout << x << " ";
        //cout << endl;
    }
    f(1,0,0,0);
    cout << cnt << endl;
}

int32_t main(){
   

     cin.tie(0); ios::sync_with_stdio(0);
     cout << fixed <<  setprecision(15);
 int t=1;//cin>> t;
 
 while(t--) solve();
 
 return 0;
}

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1552 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3016 KB Output is correct
2 Correct 2 ms 596 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9064 KB Output is correct
2 Correct 7 ms 976 KB Output is correct