oj.uz

Submission #65558

# Submission time Handle Problem Language Result Execution time Memory
65558 2018-08-08T02:33:48 Z win11905 San (COCI17_san) C++11
48 / 120
 485 ms 33776 KB 
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define pil pair<int, long>
#define x first
#define y second

const int N = 45, M = (1<<20) + 5;

int n, H[N], t[M];
long k, G[N];
vector<pil> V, V2;
vector<long> coor;
    
int get(long val) { return upper_bound(coor.begin(), coor.end(), val) - coor.begin(); }

void update(long x) {
    for(int i = get(x); i; i -= i & -i) t[i]++;
}

int query(long x) {
    int sum = 0;
    for(int i = get(x); i < M; i += i & -i) sum += t[i];
    return sum;
}

int main() {
    scanf("%d %lld", &n, &k);
    coor.emplace_back((long)(-1e18)), coor.emplace_back(0);
    int m = min(20, n);
    int z = n - m;
    long ans = 0;
    for(int i = 0; i < n; ++i) scanf("%d %lld", H+i, G+i);
    for(int i = 0; i < 1 << m; ++i) {
        long sumGold = 0;
        int last = 0;
        bool st = true;
        for(int j = 0; j < m; ++j) if(i >> j & 1) {
            if(last <= H[j]) sumGold += G[j], last = H[j];
            else { st = false; break; }
        }
        if(st) {
            V.emplace_back(last, sumGold), coor.emplace_back(sumGold);
            if(sumGold >= k) ans++;
        }    
    } 
    sort(V.begin(), V.end());
    sort(coor.begin(), coor.end());
    for(int i = 0; i < 1 << z; ++i) {
        long sumGold = 0;
        int last = 0, ft = -1;
        bool st = true;
        for(int j = 0; j < z; ++j) if(i >> j & 1) {
            if(ft == -1) ft = H[j+m];
            if(last <= H[j+m]) sumGold += G[j+m], last = H[j+m];
            else { st = false; break; }
        }
        if(st) V2.emplace_back(ft, k - sumGold);
    } 
    sort(V2.begin(), V2.end());
    update(0);
    int ptr = 0;
    for(auto x : V2) {
        while(ptr != V.size() && V[ptr].x <= x.x) update(V[ptr++].y);
        ans += query(x.y);
    }
    printf("%lld\n", ans);
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ptr != V.size() && V[ptr].x <= x.x) update(V[ptr++].y);
               ~~~~^~~~~~~~~~~
san.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
san.cpp:34:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < n; ++i) scanf("%d %lld", H+i, G+i);
                                ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 420 KB Output is correct
2 Correct 4 ms 600 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 11012 KB Output is correct
2 Correct 26 ms 11012 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 485 ms 33776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 33776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 33776 KB Output isn't correct
2 Halted 0 ms 0 KB -