APIO 2015 Solution in Code

A - Bali Sculptures.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

int n, a, b;
int y[2000];
long long sum[2001];
bool dp1[101][101];

bool ok1(long long mask) {
    dp1[0][0] = true;
    for(int i = 1; i <= b; i++)
        dp1[0][i] = false;
    for(int i = 1; i <= n; i++) {
        dp1[i][0] = false;
        for(int j = 1; j <= b; j++) {
            dp1[i][j] = false;
            for(int k = 0; k < i; k++)
                if(dp1[k][j - 1] && ((sum[i] - sum[k]) & ~mask) == 0) {
                    dp1[i][j] = true;
                    break;
                }
        }
    }
    for(int i = a; i <= b; i++)
        if(dp1[n][i])
            return true;
    return false;
}

int dp2[2001];

bool ok2(long long mask) {
    dp2[0] = 0;
    for(int i = 1; i <= n; i++) {
        dp2[i] = b + 1;
        for(int j = 0; j < i; j++)
            if(((sum[i] - sum[j]) & ~mask) == 0)
                dp2[i] = min(dp2[i], dp2[j] + 1);
    }
    return dp2[n] <= b;
}

bool ok(long long mask) {
    return a == 1 ? ok2(mask) : ok1(mask);
}

int main() {
    scanf("%d %d %d", &n, &a, &b);
    for(int i = 0; i < n; i++) {
        scanf("%d", y + i);
        sum[i + 1] = sum[i] + y[i];
    }
    long long     mask = 0x1FFFFFFFFFFLL;
    for(long long high = 0x10000000000LL; high; high >>= 1)
        if(ok(mask & ~high))
            mask &= ~high;
    printf("%lld\n", mask);
}

B - Jakarta Skyscrapers.cpp

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <limits>
using namespace std;

vector<int> ps[30000];
int dis[30000];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int s, t;
    for(int i = 0; i < m; i++) {
        int b, p;
        scanf("%d %d", &b, &p);
        ps[b].push_back(p);
        if(i == 0)
            s = b;
        else if(i == 1)
            t = b;
    }
    for(int i = 0; i < n; i++) {
        vector<int>& v = ps[i];
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
    }

    fill_n(dis, n, numeric_limits<int>::max());
    dis[s] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while(!pq.empty()) {
        int cost, where;
        tie(cost, where) = pq.top();
        pq.pop();

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
        if(where == t) {
#pragma GCC diagnostic pop
            printf("%d\n", cost);
            return 0;
        }
        if(dis[where] < cost)
            continue;

        for(int p : ps[where]) {
            for(int i = 1; where + i * p < n; i++) {
                if(dis[where + i * p] > cost + i)
                    pq.push({dis[where + i * p] = cost + i, where + i * p});
                if(binary_search(ps[where + i * p].begin(), ps[where + i * p].end(), p))
                    break;
            }
            for(int i = 1; where - i * p >= 0; i++) {
                if(dis[where - i * p] > cost + i)
                    pq.push({dis[where - i * p] = cost + i, where - i * p});
                if(binary_search(ps[where - i * p].begin(), ps[where - i * p].end(), p))
                    break;
            }
        }
    }

    puts("-1");
}

C - Palembang Bridges.cpp

#include <cstdio>
#include <utility>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <iterator>
using namespace std;

int sz;
using HW = pair<int, int>;
HW hw[100000];

multiset<int> ms;
multiset<int>::iterator mid;

long long tmp[100001];

template <typename T>
struct Nothing {
    void operator () (T, long long) {}
};

template <typename T, typename Op = Nothing<T>>
long long work(T first, T last, Op op = Op()) {
    op(first, 0);

    ms.insert(first->first);
    ms.insert(first->second);
    mid = ms.begin();
    long long sum = first->second - first->first;
    op(++first, sum);

    while(first != last) {
        ms.insert(first->first);
        ms.insert(first->second);
        sum += abs(*mid - first->first);
        sum += abs(*mid - first->second);

        if(first->second < *mid) {
            --mid;
        } else if(!(first->first < *mid)) {
            sum += 2 * *mid;
            sum -= 2 * *++mid;
        }

        op(++first, sum);
    }

    ms.clear();
    return sum;
}

int main() {
    int k, n;
    scanf("%d %d", &k, &n);
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        char p[2], q[2];
        int s, t;
        scanf("%1s %d %1s %d", p, &s, q, &t);
        if(*p == *q)
            ans += abs(s - t);
        else {
            ans++;
            hw[sz++] = minmax(s, t);
        }
    }

    if(sz) {
        if(k == 1) {
            ans += work(hw, hw + sz);
        } else {
            sort(hw, hw + sz, [](const HW& lhs, const HW& rhs) {
                 return lhs.first + lhs.second < rhs.first + rhs.second;
            });
            work(hw, hw + sz, [](HW* pp, long long x) {
                tmp[pp - hw] = x;
            });
            using R = reverse_iterator<HW*>;
            work(R(hw + sz), R(hw), [](R pp, long long x) {
                tmp[pp.base() - hw] += x;
            });
            ans += *min_element(tmp, tmp + sz + 1);
        }
    }

    printf("%lld\n", ans);
}

Thanks for the solutions!