HackerRank Superman Celebrates Diwali Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    static int n,h,i,a[2400][2400],j,k,x,y,z;
    scanf("%d%d%d",&n,&h,&z);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        for(j=0;j<x;j++)
        {
            scanf("%d",&y);
            a[y][i]++;
        }
    }
    for(i=h;i>=1;i--)
    {
        for(j=1;j<=n;j++)
        {
            if(a[i+1][j]>a[i+z][0])
            {
                a[i][j]+=a[i+1][j];
            }
            else
                a[i][j]+=a[i+z][0];
            if(a[i][j]>a[i][0])
                a[i][0]=a[i][j];
        }
    }
    printf("%d",a[1][0]);
    return 0;
}

#include<iostream>
using namespace std;

const int MAXN = 1900, MAXH = 1900;

int f[MAXN][MAXH + 1], cnt[MAXN][MAXH + 1], g[MAXH + 1];

int main()
{
	int n, h, hl;
	cin >> n >> h >> hl;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		for (int j = 0; j < num; j++)
		{
			int tmp;
			cin >> tmp;
			cnt[i][tmp]++;
		}
	}
	for (int i = 0; i < n; i++)
	{
		f[i][h] = cnt[i][h];
		if (f[i][h] > g[h])
			g[h] = f[i][h];
	}
	for (int j = h - 1; j >= 0; j--)
	{
		for (int i = 0; i < n; i++)
		{
			int 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];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
		if (f[i][0] > ans)
			ans = f[i][0];
	cout << ans << endl;
	return 0;

}

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Solution {
    static void FillSaved(int[] thisFloor, int[] savedBelow, int[] canSave, int changeBuilding)
    {
        for (int i = 0; i < thisFloor.Length; i++)
        {
            canSave[i] = Math.Max(savedBelow[i], changeBuilding) + thisFloor[i];
        }
        canSave[thisFloor.Length] = canSave.Max();
    }
    static void Main(String[] args) {
        string[] line = Console.ReadLine().Trim().Split(' ');
        int[] a = Array.ConvertAll(line, int.Parse);
        int N = a[0];
        int H = a[1];
        int I = a[2];

        int[][] building = new int[H][];
        for (int h = 0; h < H; h++)
        {
            building[h] = new int[N];
        }

        // Fill building with people
        for (int n = 0; n < N; n++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            a = Array.ConvertAll(line, int.Parse);
            for (int x = 1; x < a.Length; x++)
            {
                building[a[x] - 1][n]++;
            }
        }

        // count the number of people that can be saved starting from the first floor
        int[][] saved = new int[H][];
        for (int h = 0; h < H; h++)
        {
            saved[h] = new int[N + 1];
        }

        // First floor
        for (int n = 0; n < N; n++)
        {
            saved[0][n] = building[0][n];
        }
        saved[0][N] = building[0].Max();

        // subsequent floors
        for(int h = 1; h < H; h++)
        {
            FillSaved(building[h], saved[h - 1], saved[h], (h - I >= 0) ? saved[h - I][N]: 0);
        }
        Console.WriteLine(saved[H - 1][N]);
    }
}

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)); }
}

/* Woot! First crude draft of program earned 70.24 points (21 out of 23).
 * Cases 16 and 18 report getting the wrong answer, which feels like I've
 * overlooked some edge case. Unless maybe the program is actually running
 * out of time or memory, and it's being reported wrong. There's little bits
 * of weirdness that make me wonder if this is an old challenge. The language
 * selection is smaller than usual, most templates have a comment and no code,
 * and console.debug gets mixed with the answer on console.log.
 * 
 * Okay I checked the discussions, tuning out the code people posted, and
 * looking for references to specific test cases. One person mentions that
 * the same program on C++14 can pass 16 and 18, while on C++ it can't. So
 * that suggests the problem is time or memory.
 * 
 * OH! I've just thought of a problem in my program! The maximum number of
 * people that can be rescued would be 1900*1900! For example if all 1900
 * people in building X are on floor X, and if I=1, then Superman can get
 * the full load of people from all 1900 buildings. And 3_610_000 requires
 * 22 bits to represent. Sooooo that won't fit in Uint16! I think it'll
 * just silently overflow. Which would very cleanly explain why we got a
 * "wrong answer" instead of time or memory errors. Premature optimization
 * fail! (Also forgetting to consider this when I mentially switched from
 * using building_floor_people to represent just the input, to also using
 * it as the memoization record.) Okay, I'm going to change that 16 to a 32,
 * and try submitting this again!
 */

var DEBUG = false;

function processData(input) {
    //Enter your code here
    //let input_line_1 = /^(\d)+ (\d)+ (\d)+$/;
    //let lines = [""]; // faux type hinting?
    let lines = input.split("\n");
    
    let split_line = lines.shift().split(" ");
    let theN = parseInt(split_line[0]);
    let theH = parseInt(split_line[1]);
    let theI = parseInt(split_line[2]);
    
    let building_floor_people = new Array(theN);
    for (let b = 0; b < theN; b++) {
        let this_building = new Uint32Array(theH);
        building_floor_people[b] = this_building;
        split_line = lines[b].split(" ");
        let people_count = parseInt(split_line.shift());
        for (let p = 0; p < people_count; p++) {
            let where = parseInt(split_line[p]);
            this_building[where-1]++;
        }
    }
    
    if (DEBUG) {
        console.debug(building_floor_people);
        for (let f = 0; f < theH; f++) {
            console.debug(`${f} -> ${getBestsForFloor(building_floor_people, f)}`);
        }
    }
    
    for (let f = 1; f < theH; f++) {
        let bests = getBestsForFloor(building_floor_people, f-theI);
        for (let b = 0; b < theN; b++) {
            let here = bests[0];
            if (b === bests[1]) {
                here = bests[2];
            }
            here = Math.max(here, building_floor_people[b][f-1]);
            building_floor_people[b][f] += here;
        }
    }
    
    if (DEBUG) {
        console.debug(building_floor_people);
    }
    
    let the_very_best = getBestsForFloor(building_floor_people, theH-1)[0];
    console.log(the_very_best);
} 

/* Takes the 2D building_floor_people data, and an integer floor number. (0 index)

 * Returns an array of three values:
 * - The highest people count on that floor.
 * - The building number of where the highest was found.
 * - The second-highest people count on that floor.
 * 
 * Notes:
 * - If the floor number is negative, return [0, 0, 0]. No-one to rescue underground.
 * - If there is only a single building, the second-highest will just be zero.
 * - If multiple buildings are tied for highest, then second-highest will equal highest.
 */
function getBestsForFloor(bfp, floor) {
    let output = [0, 0, 0];
    if (floor < 0) {
        return output;
    } else if (bfp[0].length <= floor) {
        console.error("Not a valid floor number!");
    }
    for (let b = 0; b < bfp.length; b++) {
        let people_here = bfp[b][floor];
        if (people_here >= output[0]) {
            output[2] = output[0];
            output[1] = b;
            output[0] = people_here;
        } else if (people_here >= output[2]) {
            output[2] = people_here;
        }
    }
    return output;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
var _input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

l=input().split(' ')
buildings=int(l[0])
floors=int(l[1])
jump=int(l[2])
data=[]
for i in range(buildings):    
    data.append(input().split(' ')[1:])

mat=[[0 for f in range(floors+1)] for b in range(buildings)]
for l in range(len(data)):
    d={}
    for it in data[l]:
        if not it in d.keys():
            d[it]=1
        else:
            d[it]+=1
    for k in d.keys():
        mat[l][int(k)]=d[k]
        
max_per_floor=[0 for i in range(len(mat[0]))]

for f in range(1,len(mat[0])):
    for b in range(len(mat)):
        if f<jump:
            mat[b][f]=mat[b][f]+mat[b][f-1]
        else:
            mat[b][f]=max(mat[b][f]+mat[b][f-1],mat[b][f]+max_per_floor[f-jump])
    list_floors=[]
    for b in range(len(mat)):
        list_floors.append(mat[b][f])
    max_per_floor[f]=max(list_floors)

print(max_per_floor[-1])