oj.uz

Submission #16788

# Submission time Handle Problem Language Result Execution time Memory
16788 2015-09-29T08:19:11 Z gs14004 수족관 3 (KOI13_aqua3) C++14
100 / 100
 163 ms 21196 KB 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
typedef long long lint;

int x[150005], y[150005], n;
 
int h;
long long res;
 
struct rmq{
    pi tree[530000];
    int lim;
    void init(int n, int *a){
        for(lim = 1; lim <= n; lim <<= 1);
        for(int i=0; i<n; i++){
            tree[i+lim] = pi(a[i],i);
        }
        for(int i=lim-1; i; i--){
            tree[i] = min(tree[2*i],tree[2*i+1]);
        }
    }
    int q(int s, int e){
        s += lim;
        e += lim;
        pi t(1e9,1e9);
        while(s < e){
            if(s%2 == 1) t = min(t,tree[s++]);
            if(e%2 == 0) t = min(t,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) t = min(t,tree[s]);
        return t.second;
    }
}rmq;

priority_queue<lint> pq;

lint f(int s, int e){
    if(s >= e) return 0;
    int pos = rmq.q(s,e-1);
    int ph = h;
    h = y[pos];
    lint f1 = f(s, pos);
    lint f2 = f(pos+1, e);
    pq.push(min(f1, f2));
    h = ph;
    return max(f1, f2) + 1ll * (x[e] - x[s]) * (y[pos] - ph);
}
 
int main(){
    scanf("%d",&n);
    n/=2;
    for (int i=0; i<n; i++) {
        scanf("%*d %*d %d %d",&x[i],&y[i]);
    }
    rmq.init(n,y);
    pq.push(f(0, n-1));
    int k;
    scanf("%d",&k);
    lint ret = 0;
    for(int i=0; i<k && !pq.empty(); i++){
        ret += pq.top();
        pq.pop();
    }
    printf("%lld",ret);
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6524 KB Output is correct
2 Correct 0 ms 6524 KB Output is correct
3 Correct 0 ms 6524 KB Output is correct
4 Correct 0 ms 6524 KB Output is correct
5 Correct 0 ms 6524 KB Output is correct
6 Correct 0 ms 6524 KB Output is correct
7 Correct 0 ms 6524 KB Output is correct
8 Correct 0 ms 6524 KB Output is correct
9 Correct 0 ms 6524 KB Output is correct
10 Correct 0 ms 6524 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6524 KB Output is correct
2 Correct 2 ms 6524 KB Output is correct
3 Correct 0 ms 6524 KB Output is correct
4 Correct 0 ms 6524 KB Output is correct
5 Correct 0 ms 6524 KB Output is correct
6 Correct 0 ms 6592 KB Output is correct
7 Correct 0 ms 6524 KB Output is correct
8 Correct 0 ms 6524 KB Output is correct
9 Correct 2 ms 6524 KB Output is correct
10 Correct 4 ms 6524 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8064 KB Output is correct
2 Correct 53 ms 8064 KB Output is correct
3 Correct 99 ms 11824 KB Output is correct
4 Correct 92 ms 11824 KB Output is correct
5 Correct 97 ms 11828 KB Output is correct
6 Correct 92 ms 21192 KB Output is correct
7 Correct 89 ms 15332 KB Output is correct
8 Correct 143 ms 15332 KB Output is correct
9 Correct 92 ms 9600 KB Output is correct
10 Correct 91 ms 9600 KB Output is correct
11 Correct 163 ms 21196 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 8064 KB Output is correct
2 Correct 128 ms 8064 KB Output is correct
3 Correct 94 ms 11816 KB Output is correct
4 Correct 57 ms 11808 KB Output is correct
5 Correct 126 ms 11812 KB Output is correct
6 Correct 126 ms 21192 KB Output is correct
7 Correct 104 ms 15332 KB Output is correct
8 Correct 97 ms 15336 KB Output is correct
9 Correct 141 ms 9600 KB Output is correct
10 Correct 71 ms 9600 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 8064 KB Output is correct
2 Correct 101 ms 8064 KB Output is correct
3 Correct 140 ms 11812 KB Output is correct
4 Correct 162 ms 11824 KB Output is correct
5 Correct 109 ms 11816 KB Output is correct
6 Correct 146 ms 15336 KB Output is correct
7 Correct 153 ms 15332 KB Output is correct
8 Correct 96 ms 9600 KB Output is correct
9 Correct 99 ms 9600 KB Output is correct