Algorithms

<script>
var closingTag = "</div>";
var openingTag = "<div>";
</script>

Gerry Schmitz wrote:

While your example is valid, it's also not "fair".

#include <vector>
#include <algorithm>
#include <deque>
#include <stdio.h>

// if jesli starczy paliwa na cala trase
typedef unsigned long long int ulli;

using namespace std;

void sliding_window_minimum(vector<pair<ulli, ulli>> st, ulli n, ulli targetDist, ulli range)
{
    deque<pair<ulli, ulli>> minimize;
    ulli j = 0;
    for (ulli i = 0; i < n; i++)
    {
        if (st[i].first <= range)
        {
            while (!(minimize.empty()) && (minimize.back().second > st[i].second))
            {
                minimize.pop_back();
            }
            minimize.push_back(st[i]);
            j++;
        }
        else
        {
            break;
        }
    }
    for (ulli k = j; k < n; k++)
    {
        while (!(minimize.empty()) && ((st[k].first - minimize.front().first) > range))
        {
            minimize.pop_front();
        }
        if (minimize.empty()) {
            break;
        }
        ulli tempCost = st[k].second + minimize.front().second;
        while (!(minimize.empty()) && (minimize.back().second > tempCost))
        {
            minimize.pop_back();
        }
        minimize.push_back(make_pair(st[k].first, tempCost));
    }
    while (!(minimize.empty()) && ((targetDist - minimize.front().first) > range))
    {
        minimize.pop_front();
    }
    if (minimize.empty())
    {
        printf("NIE\n");
    }
    else
    {
        printf("%llu", minimize.front().second);
    }
}

int main()
{
    ulli n, d, b;
    scanf("%llu %llu %llu", &n, &d, &b);
    if (b >= d)
    {
        printf("%d", 0);
        return 0;
    }
    int temp = n;
    ulli d1, c1;
    vector<pair<ulli, ulli>> st;
    st.reserve(n+1);
    while (temp--)
    {
        scanf("%llu %llu", &d1, &c1);
        st.push_back(make_pair(d1, c1));
    }
    sliding_window_minimum(st, n, d, b);
}

Quote:

Input: A[1,..,n], n>=1

def maxi(A): # where A is a simple array that ignores the zeroth element
    m = A[1]
    i = 1
    n = len(A) - 1
    while i < n:
        if A[i+1] > A[i]: # but as Jochen points out, is wrong
            m = A[i+1]
        i += 1
    return m