oj.uz

Submission #333891

# Submission time Handle Problem Language Result Execution time Memory
333891 2020-12-08T02:19:11 Z wiwiho 3D Histogram (COCI20_histogram) C++14
20 / 110
 2500 ms 284908 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

int argmin(vector<ll>& a, int x, int y){
    return a[x] < a[y] ? x : y;
}

struct SparseTable{

    vector<vector<int>> st;

    void build(vector<ll>& a){
        int n = a.size();
        st.resize(n, vector<int>(20));
        for(int i = 0; i < n; i++) st[i][0] = i;
        for(int i = 1; i < 20; i++){
            for(int j = 0; j + (1 << i) - 1 < n; j++){
                st[j][i] = argmin(a, st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
            }
        }
    }

    int query(vector<ll>& a, int l, int r){
        int lg = __lg(r - l + 1);
        return argmin(a, st[l][lg], st[r - (1 << lg) + 1][lg]);
    }

};

int n;
vector<ll> a, b;
SparseTable sta, stb;

map<pii, ll> tmp;
ll f2(int l, int r){
    if(l > r) return 0;
    if(tmp.find(mp(l, r)) != tmp.end()) return tmp[mp(l, r)];
    int m = stb.query(b, l, r);
    tmp[mp(l, r)] = max({b[m] * (r - l + 1), f2(l, m - 1), f2(m + 1, r)});
    //cerr << l << " " << r << " " << m << " " << tmp[mp(l, r)] << "\n";
    return tmp[mp(l, r)];
}

ll f1(int l, int r){
    if(l > r) return 0;
    int m = sta.query(a, l, r);
    return max({a[m] * f2(l, r), f1(l, m - 1), f1(m + 1, r)});
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    a.resize(n);
    b.resize(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
    sta.build(a);
    stb.build(b);
    
    cout << f1(0, n - 1) << "\n";
    
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 968 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 5 ms 1356 KB Output is correct
5 Correct 34 ms 5560 KB Output is correct
6 Correct 3 ms 1072 KB Output is correct
7 Correct 2 ms 988 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 5 ms 1356 KB Output is correct
10 Correct 40 ms 5936 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 3 ms 972 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 968 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 5 ms 1356 KB Output is correct
5 Correct 34 ms 5560 KB Output is correct
6 Correct 3 ms 1072 KB Output is correct
7 Correct 2 ms 988 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 5 ms 1356 KB Output is correct
10 Correct 40 ms 5936 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 3 ms 972 KB Output is correct
13 Correct 338 ms 78760 KB Output is correct
14 Correct 259 ms 76160 KB Output is correct
15 Correct 328 ms 78184 KB Output is correct
16 Execution timed out 2591 ms 284908 KB Time limit exceeded
17 Halted 0 ms 0 KB -