Submission #655710

#	Time	Username	Problem	Language	Result	Execution time	Memory
655710		benjaminkleyn	Aliens (IOI16_aliens)	C++17	4 / 100	11 ms	340 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define COL first
#define ROW second
 
pair<ll,ll> calc(int n, int m, vector<pair<ll,ll>>& pts, ll cost)
{
    vector<ll> dp(n), cnt(n);
    for (int i = 0; i < n; i++)
    {
        dp[i] = (pts[i].COL - pts[0].ROW + 1) * (pts[i].COL - pts[0].ROW + 1) + cost;
        cnt[i] = 1;
        for (int j = 0; j < i; j++)
        {
            ll new_square = (pts[i].COL - pts[j+1].ROW + 1);
            ll overlap = max(pts[j].COL - pts[j+1].ROW + 1, 0LL);
 
            ll total_area = new_square * new_square - overlap * overlap;
 
            if (make_pair(dp[j] + total_area + cost, 1 + cnt[j]) <= make_pair(dp[i], cnt[i]))
            {
                dp[i] = dp[j] + total_area + cost;
                cnt[i] = 1 + cnt[j];
            }
        }
    }
    /*
    cout << "with a cost of " << cost << " we use " << cnt[n-1] << " squares for a total of " << dp[n-1] << '\n';
    */
    return {cnt[n-1], dp[n-1]};
}
 
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    vector<pair<ll,ll>> pts(n);
    for (int i = 0; i < n; i++)
    {
        if (r[i] > c[i])
            swap(r[i], c[i]);
        pts[i] = {c[i], r[i]};
    }
    sort(pts.begin(), pts.end());
    vector<pair<ll,ll>> monotone;
    for (int i = 0; i < n; i++)
    {
        while (monotone.size() > 0 && monotone.back().ROW >= pts[i].ROW)
            monotone.pop_back();
        monotone.push_back(pts[i]);
    }
    n = monotone.size();
 
    ll lo = 0, hi = 1e12, mid, res;
    while (lo < hi)
    {
        mid = (lo + hi) / 2;
 
        auto [count, mini] = calc(n, m, monotone, mid);
 
        if (count <= k)
            res = mid, hi = mid - 1;
        else
            lo = mid + 1;
    }
 
    auto [count, mini] = calc(n, m, monotone, res);
    return mini - k * res; 
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:68:21: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     return mini - k * res;
      |                   ~~^~~~~

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