oj.uz

Submission #81042

# Submission time Handle Problem Language Result Execution time Memory
81042 2018-10-23T15:35:51 Z ngot23 San (COCI17_san) C++11
120 / 120
 298 ms 3120 KB 
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=45;
vector <long long > v[25];
int n, b[25], cnt;
long long k, ans=0, h[N], g[N];

int get(int xx, int i) {
    return (xx>>i)&1;
}

//#define TEST

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef TEST
        freopen(".inp", "w", stdout);
        srand(time(NULL));
        int xx=rand()%15+1;
        cout << xx << ' ' << rand()%15+1 << '\n';
        rep(i, 1, xx) {
            cout << rand()%10+1 << ' ';
            cout << rand()%10+1 << '\n';
        }

    #else
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> n >> k;
  
    rep(i, 1, n)  cin >> h[i] >> g[i];
   
    int num=n>>1;
    rep(i, 1, (1ll<<num)-1) {
        cnt=0;
        rep(j, 1, num) {
            if(get(i, j-1)) b[++cnt]=j;
        }
        bool ok=0;
        rep(j, 2, cnt) {
            if(h[b[j]]<h[b[j-1]]) { ok=1; break; }
        }
        if(ok) continue;
        long long xx=0;
        rep(j, 1, cnt) {
            xx+=g[b[j]];
        }
        v[b[cnt]].push_back(xx);
        if(xx>=k) ++ans;
    }

    rep(i, 1, num) sort(v[i].begin(), v[i].end());

    int num2=n-num;
    rep(i, 1, (1ll<<num2)-1) {
        cnt=0;
        rep(j, 1, num2) {
            if(get(i, j-1)) b[++cnt]=j+num;
        }
        bool ok=0;
        rep(j, 2, cnt) {
            if(h[b[j]]<h[b[j-1]]) { ok=1; break; }
        }
        if(ok) continue;
        long long xx=0;
        rep(j, 1, cnt) xx+=g[b[j]];
        if(xx>=k) ++ans;
        rep(j, 1, num) {
            if((h[j]>h[b[1]])||(v[j].back()<(long long)k-xx)) continue;
            int id=lower_bound(v[j].begin(), v[j].end(), (long long)k-xx)-v[j].begin();
            ans+=v[j].size()-id;
        }
    }
    cout << ans;
    #endif // TEST
    return 0;
}

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 468 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 984 KB Output is correct
2 Correct 11 ms 984 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1200 KB Output is correct
2 Correct 65 ms 1200 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 3120 KB Output is correct
2 Correct 218 ms 3120 KB Output is correct