Submission #682634

#	Time	Username	Problem	Language	Result	Execution time	Memory
682634		krzsal	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	300 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

#ifdef LOCAL
ostream &operator<<(ostream &out, string str)
{
    for (char c : str)
        out << c;
    return out;
}
template <class L, class R>
ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.first << ", " << p.second << ")"; }
template <class L, class R, class S>
ostream &operator<<(ostream &out, tuple<L, R, S> p)
{
    auto &[a, b, c] = p;
    return out << "(" << a << ", " << b << ", " << c << ")";
}
template <class T>
auto operator<<(ostream &out, T a) -> decltype(a.begin(), out)
{
    out << '{';
    for (auto it = a.begin(); it != a.end(); it = next(it))
        out << (it != a.begin() ? ", " : "") << *it;
    return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts>
void dump(T a, Ts... x)
{
    cerr << a << ", ";
    dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) 42
#endif

struct ev
{
    ll cost, num, last, size;
};

ll take_photos(int m, int n, int k, vi r, vi c)
{
    vl V(n);
    for (int i = 0; i < n; i++)
        V[i] = i;
    for (int i = 0; i < m; i++)
        V[min(r[i], c[i])] = max(V[min(r[i], c[i])], ll(max(r[i], c[i])) + 1);
    int st = 0;
    while (st < n && V[st] == st)
        st++;
    if (st == n)
        return 0;
    // debug(st, V);
    ll a = 0, b = ll(n) * ll(n);
    ll ans;
    while (a < b)
    {
        ll s = (a + b) / 2;
        vector<ev> DP(n);
        DP[st] = ev{V[st] * V[st] + s, 1, 0, V[st]};
        for (int i = st + 1; i < n; i++)
        {
            ll oldCost = DP[i - 1].cost, newCost = DP[i - 1].cost + (V[i] - i) * (V[i] - i) + s;
            if (V[i] > DP[i - 1].size)
            {
                oldCost += (V[i] - DP[i - 1].last) * (V[i] - DP[i - 1].last);
                oldCost -= (DP[i - 1].size - DP[i - 1].last) * (DP[i - 1].size - DP[i - 1].last);
            }
            if (DP[i - 1].size > i)
                newCost -= (DP[i - 1].size - i) * (DP[i - 1].size - i);
            if (V[i] > DP[i - 1].size && newCost < oldCost)
                DP[i] = ev{newCost, DP[i - 1].num + 1, i, V[i]};
            else
            {
                DP[i] = DP[i - 1];
                DP[i].cost = oldCost;
            }
        }
        ans = DP.back().cost - DP.back().num * s;
        if (DP.back().num > k)
            a = s + 1;
        else
            b = s;
    }
    return ans;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40