In this HackerRank Superman Celebrates Diwali problem solution we have given the information about the occupied floors in each of the N buildings, help Superman to determine the maximum number of people he can save in one single drop from the top to the bottom floor with the given restrictions.
Problem solution in Python.
# Enter your code here. Read input from STDIN. Print output to STDOUT
n, h, hl = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
lis = list(map(int, input().split()))
for j in range(1, len(lis)):
cnt[ctr][lis[j]] += 1
for ctr in range(n):
f[ctr][h] = cnt[ctr][h]
if f[ctr][h] > g[h]:
g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
for i in range(n):
tmp = 0
if j + hl <= h:
if g[j + hl] > tmp:
tmp = g[j + hl]
if f[i][j + 1] > tmp:
tmp = f[i][j + 1]
f[i][j] = tmp + cnt[i][j]
if f[i][j] > g[j]:
g[j] = f[i][j]
ans = 0
for ctr in range(n):
ans = max(ans, f[ctr][0])
print(ans)
Problem solution in Java.
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class SupermanCelebratesDiwali {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni(), H = ni(), dr = ni();
int[][] al = new int[H+1][n];
for(int i = 0;i < n;i++){
int K = ni();
for(int j = 0;j < K;j++){
al[ni()][i]++;
}
}
int[][] dp = new int[H+2][n];
for(int h = H+1;h >= 1;h--){
int rowmax = 0;
for(int i = 0;i < n;i++){
dp[h-1][i] = Math.max(dp[h-1][i], dp[h][i] + al[h-1][i]);
rowmax = Math.max(rowmax, dp[h][i]);
}
if(h-dr >= 0){
for(int i = 0;i < n;i++){
dp[h-dr][i] = Math.max(dp[h-dr][i], rowmax + al[h-dr][i]);
}
}
}
int ret = 0;
for(int i = 0;i < n;i++){
ret = Math.max(ret, dp[0][i]);
}
out.println(ret);
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}Problem solution in C++.
#include <bits/stdc++.h>
#define REP(i, a) for (int i = 0; i < (int) (a); i ++)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); i ++)
#define MST(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 1905;
int dp[N][N], cnt[N][N], mx[N];
int n, h, d;
void calc(int height) {
REPP(i, 1, n) {
mx[height] = max(mx[height], dp[i][height]);
}
}
int main() {
scanf("%d%d%d", &n, &h, &d);
REPP(i, 1, n) {
int x, y;
cin >> x;
REP(j, x) {
scanf("%d", &y);
cnt[i][y]++;
}
}
REPP(i, 1, n) dp[i][h + 1] = 0;
calc(h + 1);
for (int i = h; i >= 0; i--) {
int pre = min(i + d, h + 1);
REPP(j, 1, n) {
dp[j][i] = dp[j][i + 1] + cnt[j][i];
dp[j][i] = max(dp[j][i], mx[pre] + cnt[j][i]);
}
calc(i);
}
cout << mx[0] << endl;
return 0;
}
Problem solution in C.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char** split_string(char*);
int main() {
int n, h, drop;
scanf("%d %d %d\n", &n, &h, &drop);
int floorlist[n][h];
for(int i = 0; i < n; i++){
for(int j = 0; j < h; j++){
floorlist[i][j] = 0;
}
char** building = split_string(readline());
int numres = atoi(building[0]);
for(int j = 0; j < numres; j++){
int floornum = atoi(building[j + 1]) - 1;
floorlist[i][floornum]++;
}
}
int bestsave[h + 1][n];
for(int i = 0; i < n; i++){
bestsave[0][i] = 0;
}
for(int i = 1; i <= h; i++){
if(i < drop){
for(int j = 0; j < n; j++){
bestsave[i][j] = bestsave[i - 1][j] + floorlist[j][i - 1];
}
}
else{
int bestjump = 0;
for(int j = 0; j < n; j++){
int check = bestsave[i - drop][j];
bestjump = (check > bestjump? check : bestjump);
}
for(int j = 0; j < n; j++){
int cand = bestsave[i - 1][j];
bestsave[i][j] = (cand > bestjump? cand : bestjump) + floorlist[j][i - 1];
}
}
}
int best = 0;
for(int i = 0; i < n; i++){
best = (bestsave[h][i] > best? bestsave[h][i] : best);
}
printf("%d", best);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
0 Comments