Submission #885958

#	Time	Username	Problem	Language	Result	Execution time	Memory
885958		normankr07	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	604 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using ll = long long;
using namespace std;

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    // Sub1
    if (n <= k && n <= 50 && m <= 100)
    {
        vector<vector<int>> arr(m + 3, vector<int>(m + 3));
        for (int i = 0; i < n; i++)
        {
            int xx = r[i], yy = c[i];
            for (int x = min(xx, yy); x <= max(xx, yy); x++)
                for (int y = min(xx, yy); y <= max(xx, yy); y++)
                {
                    arr[x][y]++;
                }
        }
        int cnt = 0;
        for (int x = 0; x <= m; x++)
            for (int y = 0; y <= m; y++)
                cnt += (arr[x][y] != 0);
        return cnt;
    }

    bool check_s2 = 1;
    for (int i = 0; i < n; i++)
        check_s2 &= (r[i] == c[i]);

    if (check_s2)
    {
        // Observation : cover (l, l), (r, r) -> cover all [(l, l), (l + 1, l + 1), ..., (r, r)]
        // For each optimal square that contain some point, the (l, l) must match one of the (r_i, r_i);
        // Sort by r_i + remove all duplicate -> Segment cover on diagonal such that sum of (r - l + 1)^2 for all ranges is minimal
        // dp[i][k] -> Cover first i points using k segment
        // dp[i][k] = min(all(dp[i'][k-1]) + (r[i-1] - l[i'] + 1) ^ 2;
        vector<pair<int, int>> pos;
        for (int i = 0; i < n; i++)
        {
            pos.push_back(make_pair(r[i], c[i]));
        }
        sort(pos.begin(), pos.end());
        pos.erase(unique(pos.begin(), pos.end()), pos.end());
        vector<vector<int>> dp(int(pos.size() + 3), vector<int>(k + 3, 0));
        n = pos.size();
        for (int i = 0; i < n; i++)
        {
            for (int dk = 1; dk <= k; dk++)
            {
                int mindp = 1e9, minindex = -1;
                for (int ii = 0; ii < i; ii++)
                    if (dp[ii][dk - 1] < mindp)
                    {
                        minindex = ii;
                        mindp = dp[ii][dk - 1];
                    }
                long long dd = max(0, (pos[i - 1].first - pos[minindex].second + 1) *
                                          (pos[i - 1].first - pos[minindex].second + 1));
                dp[i][dk] = mindp + dd * dd;
            }
        }
        return dp[n - 1][k];
    }
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

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