Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Meteor CodeChef Solution
Problem -Meteor CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>
Meteor CodeChef Solution in C++17
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "complex"
using namespace std;
using namespace __gnu_pbds;
template <class T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
typedef pair<int, int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(), a.end()
#define SET(a, b) memset(a, b, sizeof(a))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define si(n) scanf("%d", &n)
#define dout(n) printf("%d\n", n)
#define sll(n) scanf("%lld", &n)
#define lldout(n) printf("%lld\n", n)
#define fast_io \
ios_base::sync_with_stdio(false); \
cin.tie(NULL)
#define endl "\n"
const long long mod = 1e9 + 7;
void prec() {
}
void solve() {
// dp[i][j] is the answer between the rows i and j
// dp[i][j]= max(dp[i+1][j],dp[i][j-1])
// add max area that can be created so that upper row is i and lower is j
// so get max width basically
//
int n, m, k;
cin >> n >> m >> k;
bool A[n][m];
memset(A, true, sizeof(A));
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
x--;
y--;
A[x][y] = false;
}
int up[n][m];
memset(up, 0, sizeof(up));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
up[i][j] = A[i][j] ? 1 : 0;
if (i && A[i][j]) {
up[i][j] += up[i - 1][j];
}
}
}
int left[n][m];
int right[n][m];
for (int i = 0; i < n; i++) {
stack<pair<int, int>> s;
for (int j = 0; j < m; j++) {
int x = up[i][j];
right[i][j] = m - 1;
if (!s.size()) {
s.push({up[i][j], j});
continue;
}
while (s.size() && s.top().first > x) {
right[i][s.top().second] = j - 1;
s.pop();
}
s.push({up[i][j], j});
}
while (s.size()) {
s.pop();
}
for (int j = m - 1; j >= 0; j--) {
int x = up[i][j];
left[i][j] = 0;
if (!s.size()) {
s.push({up[i][j], j});
continue;
}
while (s.size() && s.top().first > x) {
left[i][s.top().second] = j + 1;
s.pop();
}
s.push({up[i][j], j});
}
}
// now we can find that for i and j, what is the maximum
int c[n][n];
memset(c, 0, sizeof(c));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (A[i][j]) {
int x = right[i][j] - left[i][j] + 1;
int y = up[i][j];
c[i - y + 1][i] = max(c[i - y + 1][i], x);
}
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << c[i][j] << " ";
// }
// cout << endl;
// }
int fdp[n][n];
memset(fdp, 0, sizeof(fdp));
// apply dp on c
for (int i = 0; i < n; i++) {
for (int l = n; l; l--) {
int j = i + l - 1;
if (j >= n) {
continue;
}
fdp[i][j] = c[i][j];
if (i) {
fdp[i][j] = max(fdp[i][j], fdp[i - 1][j]);
}
if (j < n - 1) {
fdp[i][j] = max(fdp[i][j], fdp[i][j + 1]);
}
}
}
// cout << endl;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << fdp[i][j] << " ";
// }
// cout << endl;
// }
int dp[n][n];
memset(dp, 0, sizeof(dp));
for (int l = 1; l <= n; l++) {
// dp[i][i] = fdp[i][i];
for (int i = 0; i < n; i++) {
int j = i + l - 1;
if (l == 1) {
dp[i][i] = fdp[i][i];
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
dp[i][j] = max(dp[i][j], fdp[i][j] * (j - i + 1));
}
}
}
// cout << endl;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << fdp[i][j] << " ";
// }
// cout << endl;
// }
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
l--;
r--;
cout << dp[l][r] << endl;
}
}
signed main() {
fast_io;
prec();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int totalTests = 1;
// cin >> totalTests;
for (int testNo = 1; testNo <= totalTests; testNo++) {
// cout << "Case #" << testNo << ": ";
solve();
}
return 0;
}Meteor CodeChef Solution in C++14
#include <cstdio>
#include <cctype>
using namespace std;
const int N=1511; bool ban[N][N];
int dp[N][N],n,m,k,h[N],w[N],st[N],Top;
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
void Max(int &x,int y){x=x>y?x:y;}
int main(){
n=iut(),m=iut(),k=iut();
for (int i=1;i<=k;++i){
int x=iut(),y=iut();
ban[x][y]=1;
}
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j)
if (ban[i][j]) h[j]=0;
else ++h[j];
Top=0;
for (int j=1;j<=m+1;++j){
int width=0;
while (Top&&h[st[Top]]>=h[j]){
width+=w[Top];
Max(dp[i-h[st[Top]]+1][i],width);
--Top;
}
st[++Top]=j,w[Top]=width+1;
}
for (int j=1;j<i;++j) Max(dp[j+1][i],dp[j][i]);
for (int j=1;j<=i;++j) dp[j][i]*=i-j+1;
}
for (int len=1;len<n;++len)
for (int i=1;i+len<=n;++i)
Max(dp[i][i+len],dp[i][i+len-1]),
Max(dp[i][i+len],dp[i+1][i+len]);
for (int Q=iut();Q;--Q){
int l=iut(),r=iut();
print(dp[l][r]),putchar(10);
}
return 0;
}Meteor CodeChef Solution in C
#include<stdio.h>
int a[1002][1002],dp[1002][1002],left[1002],right[1002],mark[1005];
int n,m,k;
struct Stack {
int height,cnt;
}stak[1002];
inline int inp()
{
int noRead=0;
char p=getchar_unlocked();
for(;p<33;){p=getchar_unlocked();};
while(p>32)
{
noRead = (noRead << 3) + (noRead << 1) + (p - '0');
p=getchar_unlocked();
}
return noRead;
};
int max(int a,int b)
{ return (a>b?a:b); }
void calc()
{
int i,j,top,cnt,width;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]==0)
a[i][j]=a[i-1][j]+1;
else
a[i][j]=0;
}
}
for(i=1;i<=n;i++)// Current row we are on
{
top=-1;
for(j=1;j<=m;j++)
{
cnt=0;
while(top>=0 && stak[top].height>=a[i][j])
{
cnt+=stak[top].cnt;
top--;
}
stak[++top].height=a[i][j];
stak[top].cnt=cnt+1;
left[j]=stak[top].cnt;
}
top=-1;
for(j=m;j>=1;j--)
{
cnt=0;
while(top>=0 && stak[top].height>=a[i][j])
{
cnt+=stak[top].cnt;
top--;
}
stak[++top].height=a[i][j];
stak[top].cnt=cnt+1;
right[j]=stak[top].cnt;
}
for(j=1;j<=i;j++) mark[j]=0;
for(j=1;j<=m;j++)// max width for each height on this row
{
width=left[j]+right[j]-1;
mark[a[i][j]]=max(width,mark[a[i][j]]);
}
width=0;
for(j=1;j<=i;j++)
{
width=max(width,mark[i-j+1]);// rectangle with height x is contained in rectangle with height x+1
dp[j][i]=(i-j+1)*width;
}
for(j=i;j>=1;j--)
dp[j][i]=max(dp[j][i],max(dp[j+1][i],dp[j][i-1]));
}
}
int main()
{
int x,y,q,l,h;
n=inp();m=inp();k=inp();//scanf("%d%d%d",&n,&m,&k);
while(k--)
{
x=inp();y=inp();//scanf("%d%d",&x,&y);
a[x][y]=1;
}
calc();
q=inp();//scanf("%d",&q);
while(q--)
{
l=inp();h=inp();//scanf("%d%d",&l,&h);
printf("%d\n",dp[l][h]);// =dp[l+1][r],dp[l][r-1],max rect with height(r-l+1) and base r
}
return 0;
}Meteor CodeChef Solution in JAVA
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
class Meteor {
private void solve(InputReader in, PrintWriter out) {
int N = in.nextInt();
int M = in.nextInt();
int K = in.nextInt();
int[] X = new int[K + 1];
int[] Y = new int[K + 1];
for (int i = 1; i <= K; i++) {
X[i] = in.nextInt();
Y[i] = in.nextInt();
}
int Q = in.nextInt();
int[] L = new int[Q + 1];
int[] H = new int[Q + 1];
for (int i = 1; i <= Q; i++) {
L[i] = in.nextInt();
H[i] = in.nextInt();
}
boolean[][] danger = new boolean[N + 1][M + 1];
for (int i = 1; i <= K; i++) {
danger[X[i]][Y[i]] = true;
}
int[][] up = new int[N + 1][M + 1];
int[][] left = new int[N + 1][M + 1];
int[][] right = new int[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (danger[i][j]) {
up[i][j] = 0;
} else {
up[i][j] = up[i - 1][j] + 1;
}
}
}
// left[i][j] is the first column k on the left side of j,
// such that up[i][k] is smaller than up[i][j]
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
left[i][j] = j - 1;
while (left[i][j] > 0 && up[i][left[i][j]] >= up[i][j]) {
left[i][j] = left[i][left[i][j]];
}
}
}
// right[i][j] is the first column k on the right side of j,
// such that up[i][k] is smaller than up[i][j]
for (int i = 1; i <= N; i++) {
for (int j = M; j >= 1; j--) {
right[i][j] = j + 1;
while (right[i][j] <= M && up[i][right[i][j]] >= up[i][j]) {
right[i][j] = right[i][right[i][j]];
}
}
}
int[][] wMax = new int[N + 1][N + 1]; // max width
int[][] ans = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) if (!danger[i][j]) {
int h = up[i][j];
wMax[i - h + 1][i] = Math.max(wMax[i - h + 1][i], right[i][j] - left[i][j] - 1);
}
// smaller heights are eligible for width as their parent
for (int j = 1; j <= i; j++) {
wMax[j][i] = Math.max(wMax[j][i], wMax[j - 1][i]);
}
}
// max area from wMax
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j++) {
ans[i][j] = Math.max(ans[i][j], (j - i + 1) * wMax[i][j]);
}
}
// spread out the inner ones
for (int h = 0; h < N; h++) {
for (int i = 1; i + h <= N; i++) {
int j = i + h;
if (i - 1 >= 1) ans[i - 1][j] = Math.max(ans[i - 1][j], ans[i][j]);
if (j + 1 <= N) ans[i][j + 1] = Math.max(ans[i][j + 1], ans[i][j]);
}
}
for (int i = 1; i <= Q; i++) {
out.println(ans[L[i]][H[i]]);
}
}
public static void main(String[] args) {
InputReader in = new InputReader();
PrintWriter out = new PrintWriter(System.out);
Meteor solver = new Meteor();
solver.solve(in, out);
out.close();
}
}
class InputReader {
private InputStream stream = System.in;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public int read() {
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}Meteor CodeChef Solution in C#
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace Meteor
{
class Program
{
static int N;
static int M;
static bool[,] Map;
static int[,] MaxDepth;
static int[,] MaxArea;
static bool IsClean(int n, int m, int d)
{
for (int di = 0; di < d; ++di)
{
if (Map[n, m + di])
return false;
}
return true;
}
static void ExploreRectangle(int n, int m, int d, int w)
{
while (n + w < N && IsClean(n + w, m, d))
++w;
MaxDepth[w, n] = Math.Max(MaxDepth[w, n], d);
if (n + w < N)
{
for (int di = 0; di < d; ++di)
{
if (!Map[n + w, m + di] && (di == 0 || Map[n + w, m + di - 1]))
{
int di2 = 1;
while (di + di2 < d && !Map[n + w, m + di + di2])
++di2;
if (n == 0 || !IsClean(n - 1, m + di, di2))
ExploreRectangle(n, m + di, di2, w + 1);
}
}
}
}
static void Main(string[] args)
{
string[] NMK = Console.ReadLine().Split(' ');
N = Convert.ToInt32(NMK[0]);
M = Convert.ToInt32(NMK[1]);
int K = Convert.ToInt32(NMK[2]);
Map = new bool[N, M];
for (int k = 0; k < K; ++k)
{
string[] xy = Console.ReadLine().Split(' ');
int x = Convert.ToInt32(xy[0]);
int y = Convert.ToInt32(xy[1]);
Map[x - 1, y - 1] = true;
}
MaxDepth = new int[N + 1, N];
for (int n = 0; n < N; ++n)
for (int m = 0; m < M; ++m)
{
if (!Map[n, m] && (m == 0 || Map[n, m - 1]))
{
int d = 1;
while (m + d < M && !Map[n, m + d])
++d;
if (n == 0 || !IsClean(n - 1, m, d))
ExploreRectangle(n, m, d, 1);
}
}
for (int w = N; w > 1; --w)
for (int n = 0; n <= N - w; ++n)
{
MaxDepth[w - 1, n] = Math.Max(MaxDepth[w - 1, n], MaxDepth[w, n]);
MaxDepth[w - 1, n + 1] = Math.Max(MaxDepth[w - 1, n + 1], MaxDepth[w, n]);
}
MaxArea = new int[N + 1, N];
for (int w = 1; w <= N; ++w)
for (int n = 0; n <= N - w; ++n)
MaxArea[w, n] = w * MaxDepth[w, n];
for (int w = 2; w <= N; ++w)
for (int n = 0; n <= N - w; ++n)
MaxArea[w, n] = Math.Max(MaxArea[w, n], Math.Max(MaxArea[w - 1, n], MaxArea[w - 1, n + 1]));
int Q = Convert.ToInt32(Console.ReadLine());
using (var stream = Console.OpenStandardOutput())
{
var writer = new StreamWriter(stream);
for (int q = 0; q < Q; ++q)
{
string[] LH = Console.ReadLine().Split(' ');
int L = Convert.ToInt32(LH[0]);
int H = Convert.ToInt32(LH[1]);
writer.WriteLine(MaxArea[H - L + 1, L - 1]);
}
writer.Flush();
}
}
}
}Meteor CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
n, m, k := readThreeNums(reader)
bad := make([][]int, k)
for i := 0; i < k; i++ {
bad[i] = readNNums(reader, 2)
}
q := readNum(reader)
Q := make([][]int, q)
for i := 0; i < q; i++ {
Q[i] = readNNums(reader, 2)
}
res := solve(n, m, bad, Q)
var buf bytes.Buffer
for i := 0; i < len(res); i++ {
buf.WriteString(fmt.Sprintf("%d\n", res[i]))
}
fmt.Print(buf.String())
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func solve(n int, m int, bad [][]int, Q [][]int) []int {
field := make([][]int, n)
for i := 0; i < n; i++ {
field[i] = make([]int, m)
}
for _, cur := range bad {
a, b := cur[0], cur[1]
field[a-1][b-1] = 1
}
height := make([][]int, n+1)
height[n] = make([]int, m)
for i := n - 1; i >= 0; i-- {
height[i] = make([]int, m)
for j := 0; j < m; j++ {
if field[i][j] == 0 {
height[i][j] = 1 + height[i+1][j]
} else {
height[i][j] = 0
}
}
}
stack := make([]Pair, m)
width := make([][]int, n)
for r := 0; r < n; r++ {
width[r] = make([]int, n+1)
var p int
stack[p] = Pair{height[r][0], 0}
p++
for c := 1; c < m; c++ {
cur := height[r][c]
last := c
for p > 0 && stack[p-1].first > cur {
width[r][r+stack[p-1].first-1] = max(width[r][r+stack[p-1].first-1], c-stack[p-1].second)
last = stack[p-1].second
p--
}
if p == 0 || stack[p-1].first < cur {
stack[p] = Pair{height[r][c], last}
p++
}
}
for p > 0 {
if r+stack[p-1].first-1 >= 0 {
width[r][r+stack[p-1].first-1] = max(width[r][r+stack[p-1].first-1], m-stack[p-1].second)
}
p--
}
for rr := n - 1; rr >= r; rr-- {
width[r][rr] = max(width[r][rr], width[r][rr+1])
}
for rr := r; rr < n; rr++ {
width[r][rr] *= rr - r + 1
}
}
for l := 2; l <= n; l++ {
for r := 0; r+l-1 < n; r++ {
width[r][r+l-1] = max(width[r][r+l-1], width[r][r+l-2])
width[r][r+l-1] = max(width[r][r+l-1], width[r+1][r+l-1])
}
}
res := make([]int, len(Q))
for i, cur := range Q {
a, b := cur[0], cur[1]
a--
b--
res[i] = width[a][b]
}
return res
}
type Pair struct {
first int
second int
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}Meteor CodeChef Solution Review:
In our experience, we suggest you solve this Meteor CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Meteor CodeChef Solution.
Conclusion:
I hope this Meteor CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
