Submission #1160082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160082		ocasu	3D Histogram (COCI20_histogram)	C++20	20 / 110	2590 ms	19016 KiB

histogram

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    int n; cin>>n;
    vector<int> a(n), b(n);
    for (int i=0; i<n; i++) cin>>a[i]>>b[i];
    int ans=0;
    //cout<<'\n';
    for (int i=0; i<n; i++){
        int aL=-1, bL=-1, aR=-1, bR=-1;
        for (int j=i-1; j>=0; j--) if (a[j] < a[i]) {
            aL=a[j];
            break;
        }
        for (int j=i-1; j>=0; j--) if (b[j] < b[i]) {
            bL=b[j];
            break;
        }
        for (int j=i+1; j<n; j++) if (a[j] < a[i]) {
            aL=a[j];
            break;
        }
        for (int j=i+1; j<n; j++) if (b[j] < b[i]) {
            bL=b[j];
            break;
        }
        //cout<<a[i]<<' '<<b[i]<<'\n';
        vector<pair<int,int>> cands = {{a[i], b[i]}, {a[i], bL}, {a[i], bR}, {aL, b[i]}, {aR, b[i]}, {aL, bL}, {aL, bR}, {aR,bL}, {aR,bR}};
        for (int x=0; x<n; x++){
            cands.push_back({a[i], b[x]});
            cands.push_back({a[x], b[i]});

        }
        for (auto [height, length]: cands) {
            int l=-1, r=n;
            for (int j=i; j>=0; j--) if (a[j]<height) {
                l=max(l,j);
                break;
            }
            for (int j=i; j>=0; j--) if (b[j]<length) {
                l=max(l,j);
                break;
            }
            for (int j=i; j<n; j++) if (a[j]<height) {
                r=min(r,j);
                break;
            }
            for (int j=i; j<n; j++) if (b[j]<length) {
                r=min(r,j);
                break;
            }
            l++, r--;
            //if (height==15 and length==19){
            //    cout<<l<<' '<<r<<'\n';
            //}
            if (l<=r){
                ans=max(ans, length*height*(r-l+1));
            }
        } 
    }
    cout<<ans<<'\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 90