HackerRank Billboards problem solution

In this HackerRank Billboards problem solution we have given n, k, and the revenue of each of the n billboards, find and print the maximum profit that ADZEN can earn while complying with the zoning ordinance. Assume that Main street is a straight, contiguous block of n billboards that can be removed but cannot be reordered in any way.

Problem solution in Python.

#!/bin/python3

import os
import sys

#
# Complete the billboards function below.
#
def billboards(k, revenue):
    N = len(revenue)
    
    total = sum(revenue)
    
    if k == N:
        return total
    else:
        x = revenue[: k + 1]
        
        min_value = min(x)
        min_index = x.index(min_value)
        
        for i in range(k + 1, N):
            if i - min_index >= k:
                min_value = min(x[i - (k + 1) : i + 1])
                min_index = x.index(min_value)
            
            x.append(min_value + revenue[i])
            
            if x[i] < min_value:
                min_value = x[i]
                min_index = i
        
        return total - min(x[N - (k + 1) :])

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    revenue = []

    for _ in range(n):
        revenue_item = int(input())
        revenue.append(revenue_item)

    result = billboards(k, revenue)

    fptr.write(str(result) + 'n')

    fptr.close()

Problem solution in Java.

import java.util.Scanner;

public class Billboards {

    static int n;
    static int k;
    static long a[];
    static long f[];
    static int heap[];
    static int heapSize;
    static int where[];

    static void swap(int a[], int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    static boolean lessThan(int i, int j) {
        return f[i - 1] + a[i] < f[j - 1] + a[j];
    }

    static void siftUp(int i) {
        if (i > 1 && lessThan(heap[i], heap[i / 2])) {
            swap(heap, i, i / 2);
            swap(where, heap[i], heap[i / 2]);
            siftUp(i / 2);
        }
    }

    static void siftDown(int i) {
        int which = i;
        if (2 * i <= heapSize && lessThan(heap[2 * i], heap[which])) which = 2 * i;
        if (2 * i + 1 <= heapSize && lessThan(heap[2 * i + 1], heap[which])) which = 2 * i + 1;
        if (which != i) {
            swap(heap, i, which);
            swap(where, heap[i], heap[which]);
            siftDown(which);
        }
    }

    static void insert(int element) {
        where[element] = ++heapSize;
        heap[heapSize] = element;
        siftUp(heapSize);
    }

    static void remove(int element) {
        if (where[element] < heapSize) {
            where[heap[heapSize]] = where[element];
            heap[where[element]] = heap[heapSize--];

            siftDown(where[element]);
            siftUp(where[element]);
        } else heapSize--;
        where[element] = 0;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        n = cin.nextInt();
        k = cin.nextInt();
        a = new long[n + 1];
        f = new long[n + 1];
        heap = new int[n + 1];
        where = new int[n + 1];

        long sum = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = cin.nextLong();
            sum += a[i];
        }

        for (int i = 1; i <= k; i++)
            insert(i);
        for (int i = k + 1; i <= n; i++) {
            insert(i);
            f[i] = f[heap[1] - 1] + a[heap[1]];
            remove(i - k);
        }

        System.out.println(sum - f[n]);

        cin.close();
    }
}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include <iostream>
#include <queue>
#include <vector>
#include <math.h>

using namespace std;

struct Profit {
    long long value;
    int pos;
};

class CompareProfit {
    public:
    bool operator()(Profit& t1, Profit& t2)
    {
        return t1.value > t2.value;
    }
};

int main(int argc, char** argv) {
    int N, K;
    std::cin >> N >> K;
    
    long long curr;
    std::priority_queue<Profit, vector<Profit>, CompareProfit> q;
    
    Profit p;
    Profit p2;
    long long sum = 0;
    
    for (int i = 0; i < N; i++) {
        std::cin >> curr;
        sum += curr;
        
        if (K!=N) {
            if (i <= K) {
                p.value = curr;
                p.pos = i;
                q.push(p);
            } else {
                p = q.top();
                while (p.pos < i - (K+1)) {
                    q.pop();
                    p = q.top();
                }
                p2.value = curr + p.value;
                p2.pos = i;
                q.push(p2);
            }
        }
    }
    if (K == N) {
        std::cout << sum << std::endl;
    } else {
        p = q.top();
        while(p.pos < N - (K+1)) {
            q.pop();
            p = q.top();
        }
        std::cout << (sum - p.value) << std::endl;
    }
    return 0;
}

Problem solution in C.

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

int main(){

	int n,k,i,j;
	
	scanf("%d %d",&n,&k);
	long int *v=(long int *)malloc((n+1)*sizeof(long int));
	long int *p=(long int *)malloc((n+1)*sizeof(long int));	
	
	for(i=1;i<=n;i++)
		scanf("%ld",&v[i]);

	v[0]=0;
	for(i=1;i<=n;i++)
		v[i]+=v[i-1];
	
	for(i=1;i<=k;i++)
		p[i]=v[i];

	long int removed;
	int maxi=-1;
	for(i=k+1;i<=n;i++){
		if(maxi>0 && v[i]-v[i-1]>removed) {
			p[i]=p[i-1]+v[i]-v[i-1];
			maxi--;
		}
		else{
			long int max=-1;
			j=i-k;
			while(j<=i){
				long int profit=p[j-1]+(v[i]-v[j]);
				if(profit>max) {max=profit; maxi=j-i+k; removed=v[j]-v[j-1];}
				j++;
			}
			p[i]=max;
		}
	}
		
	printf("%ldn",p[n]);
	
return 0;
}