SPOJ

aba12c.cpp

// DP
// Source: https://www.spoj.com/status/ABA12C
#include <iostream>
#include <climits>
#include <vector>
#define INF (INT_MAX / 2)
using namespace std;

int main(void)
{
    int C;
    cin >> C;
    while (C--)
    {
        // inputs:
        int N; // number of friends
        int K; // how much apple he wants to buy in kilogram?
        cin >> N >> K;

        vector<int> price(K + 1);
        for (int i = 1; i <= K; i++)
        {
            cin >> price[i];
            if (price[i] == -1)
                price[i] = INF;
        }

        // initialization:
        vector<int> buy(K + 1, INF);
        buy[0] = 0;
        buy[1] = price[1];

        for (int x = 2; x <= K; x++)     // for each particular weigths,
            for (int j = 1; j <= x; j++) // try possible packets.
                buy[x] = min(buy[x], price[j] + buy[x - j]);

        if (buy[K] == INF)
            cout << "-1\n";
        else
            cout << buy[K] << "\n";
    }
}

addrev.cpp

// Ad-hoc
// Source: https://www.spoj.com/problems/ADDREV/
#include <iostream>
using namespace std;

int reverse(int n)
{
    int res = 0;
    while (n != 0)
    {
        res = res*10 + n%10;
        n /= 10;
    }
    return res;
}

int main(void)
{
    int t; cin >> t;

    for (int i = 0; i < t; i++)
    {
        int a, b; cin >> a >> b;
        int c = reverse(a) + reverse(b);
        cout << reverse(c) << endl;
    }
}

alien.cpp

// Sliding Window
// Source: https://www.spoj.com/status/ALIEN
#include <iostream>
using namespace std;

constexpr int MAXN = 1e5;
int a[MAXN];

int main(void)
{
    int T;
    cin >> T;
    while (T--)
    {
        int N; // number of stations
        int B; // maximum people the alien is ok with
        cin >> N >> B;

        for (int i = 0; i < N; i++)
            cin >> a[i];

        int i = 0;       // opening index of the current window
        int station = 0; // number of stations in the best passage
        int people = 0;  // number of people seen in the best passage

        for (int j = 0, s = 0, p = 0; j < N; j++)
        // j: closing index of the slide
        // s: total station in the current window
        // p: total people in the current window
        {
            s++;
            p += a[j];

            while (p > B)
            {
                p -= a[i];
                i++;
                s--;
            }

            if (s > station)
            {
                station = s;
                people = p;
            }
            else if (s == station)
            {
                people = min(p, people);
            }
        }

        cout << people << " " << station << "\n";
    }
}

micemaze.cpp

// BFS
// Source: https://www.spoj.com/problems/MICEMAZE/
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

constexpr int MAXN = 1e2;
constexpr int INF = INT_MAX / 2;
vector<pair<int, int>> adj[MAXN];
int dist[MAXN];
bool visited[MAXN];

int main(void)
{
    int n; // number of cells in the maze
    int e; // the number of the exit cell
    int t; // starting value for the count-down timer
    cin >> n >> e >> t;

    e--;

    // connections in the maze:
    {
        int m; // number of connections in the maze
        cin >> m;
        int u, v; // adjacent cells of the maze
        int w;    // time required to travel from u to v.

        while (m--)
        {
            cin >> u >> v >> w;
            adj[u - 1].push_back({v - 1, w});
        }
    }

    // BFS: O(n + m)
    queue<int> q;
    auto bfs = [&](int s) {
        dist[s] = 0;
        visited[s] = true;
        q.push(s);

        while (!q.empty())
        {
            int u = q.front();
            q.pop();

            for (auto x : adj[u])
            {
                int v = x.first;
                int d = x.second;
                if (visited[v])
                {
                    dist[v] = min(dist[v], dist[u] + d);
                    continue;
                }
                visited[v] = true;
                dist[v] = dist[u] + d;
                q.push(v);
            }
        }
        return dist[e] <= t;
    };

    int ans = 0; // number of mice that reached the exit cell before time-up
    for (int i = 0; i < n; i++)
    {
        fill(dist, dist + n, INF);
        fill(visited, visited + n, false);
        ans += bfs(i);
    }

    cout << ans << "\n";
}

nakanj.cpp

// BFS
// Source: https://www.spoj.com/status/NAKANJ
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int dist[64];
bool visited[64];

void init()
{
    fill(visited, visited + 64, false);
}

int xs[] = {-1, 1, -1, 1, -2, 2, -2, 2};
int ys[] = {-2, -2, 2, 2, -1, -1, 1, 1};

void bfs(int i, int j)
{ // source: [i, j]
    int s = (i * 8) + j;
    visited[s] = true;
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            int r = (u / 8) + xs[i];
            int c = (u % 8) + ys[i];
            if (r < 0 || r >= 8 || c < 0 || c >= 8)
                continue;

            int v = (r * 8) + c;
            if (visited[v])
                continue;

            dist[v] = dist[u] + 1;
            visited[v] = true;
            q.push(v);
        }
    }
}

int main(void)
{
    int T;
    cin >> T;
    while (T--)
    {
        init();
        string u, v;
        cin >> u >> v;

        int i = u[0] - 'a';
        int j = u[1] - '1';
        bfs(i, j);

        int r = v[0] - 'a';
        int c = v[1] - '1';
        cout << dist[r * 8 + c] << "\n";
    }
}

thrbl.cpp

// Sparse Table
// Source: https://www.spoj.com/status/THRBL
#include <iostream>
#include <cmath>
using namespace std;

constexpr int MAXN = 50000;
constexpr int K = 16;
int a[MAXN];
int table[MAXN][K];

int main(void) {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> a[i];

    for (int i = 0; i < N; i++) table[i][0] = a[i];
    for (int j = 1; j < K; j++)
        for (int i = 0; i + (1 << j) <= N; i++)
            table[i][j] = max(table[i][j-1], table[i + (1 << (j-1))][j-1]);

    int nsuccess = 0;
    while (M--) {
        int L, R;
        cin >> L >> R;

        if (R - L <= 1) {
            nsuccess++;
            continue;
        }

        L -= 1;
        R -= 2;

        int j = log2(R - L + 1);
        int highest = max(table[L][j], table[R - (1 << j) + 1][j]);
        if (a[L] == highest) nsuccess++;
    }
    cout << nsuccess << "\n";
}

water.cpp

// BFS
// Source: https://www.spoj.com/status/WATER
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int grid[100][100];
int xs[] = {-1, 0, 0, 1};
int ys[] = {0, -1, 1, 0};

int main(void)
{
    int T;
    cin >> T;

    while (T--)
    {
        int N, M;
        cin >> N >> M;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                cin >> grid[i][j];

        vector<bool> visited(N * M);
        priority_queue<pair<int, int>, vector<pair<int, int>>,
                       greater<pair<int, int>>>
            q; // {height, row-major-index}

        for (int i = 0; i < N; i++)
        {
            q.push({grid[i][0], i * M});
            visited[i * M] = true;
            q.push({grid[i][M - 1], i * M + M - 1});
            visited[i * M + M - 1] = true;
        }

        for (int j = 1; j < M - 1; j++)
        {
            q.push({grid[0][j], j});
            visited[j] = true;
            q.push({grid[N - 1][j], M * (N - 1) + j});
            visited[M * (N - 1) + j] = true;
        }

        long long puddle = 0;
        while (!q.empty())
        {
            auto cell = q.top();
            q.pop();
            int idx = cell.second;

            for (int i = 0; i < 4; i++)
            {
                int r = (idx / M) + xs[i];
                int c = (idx % M) + ys[i];
                if (r <= 0 || r >= N || c <= 0 || c >= M)
                    continue;
                if (visited[r * M + c])
                    continue;

                puddle += max(0, cell.first - grid[r][c]);
                grid[r][c] = max(grid[r][c], cell.first);
                q.push({grid[r][c], r * M + c});
                visited[r * M + c] = true;
            }
        }
        cout << puddle << "\n";
    }
}