5
Original Problem: Problem 2सबसे बड़ा खाली आयत जिसका आधार x- अक्ष
पर एक आयताकार स्थान जिसकी ऊंचाई 500 है और चौड़ाई 10^5 है, तो हम एन अंक दिया जाता है।
हमें सबसे बड़ा उप-आयताकार पता होना चाहिए जिसका आधार एक्स-अक्ष पर है और इसमें उचित बिंदुओं में से कोई भी बिंदु नहीं है (लेकिन उन्हें अपने किनारों में शामिल किया जा सकता है)।
#include <iostream>
#include <algorithm>
const int nWidth = 100000;
const int nHeight = 500;
int main(){
int *nMaxHeights = new int[nWidth];
std::fill (nMaxHeights, nMaxHeights+nWidth, nHeight);
int N;
std::cin >> N;
for (int x,y,iii=0; iii < N; iii++){
std::cin >> x >> y;
nMaxHeights[x] = std::min(y+1, nMaxHeights[x]);
}
int maxArea = 0;
for (int jjj,iii=0; iii < nWidth; iii++){
for (jjj=iii; jjj < nWidth; jjj++){
if (nMaxHeights[jjj] < nMaxHeights[iii])
break;
}
maxArea = std::max((jjj-iii+1)*nMaxHeights[iii],maxArea);
}
std::cout << maxArea;
return 0;
}
यह काम करता है, फिर भी स्पष्ट रूप से एक टीएलई (निष्पादन समय सीमा पार हो गई) प्राप्त करता है:
मैं एक हे (चौड़ाई^2) कलन विधि की कोशिश की।
मैं बेहतर कैसे कर सकता हूं?