Submission #599020

#	Time	Username	Problem	Language	Result	Execution time	Memory
599020		jophyyjh	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	312 KiB

aliens

/**
 * I don't feel like fully solving this, so maybe i'll just score some partials.
 * 
 * [S1] Too trivial
 * [S2] Each point lies on the main diagonal. Clearly, no two squares should have
 *      common squares, which means the points are partitioned into contiguous
 *      segments. O(n^2 * k) dp kills it.
 * [S3] Maybe we can somehow sort the points based on their columns, then apply [S2]?
 *      Yep, pretty much analagous to [S2]. The key here is that if (2,5), (3,5),
 *      the square that covers (2,5) must cover (3,5).
 * 
 * Time Complexity: O(n^2 * k)
 * Implementation 1
*/

#include <bits/stdc++.h>
#include "aliens.h"

typedef long long   ll;

const int N_MAX = 500;
const ll INF = 0x3f3f3f3f3f3f;

inline ll sqr(int k)    { return ll(k) * ll(k); }


struct seg_t {
    int i, j;
};

ll cover[N_MAX + 1][N_MAX + 1];

ll take_photos(int n, int m, int max_sqr, std::vector<int> row, std::vector<int> col) {
    std::vector<seg_t> values(n);
    for (int k = 0; k < n; k++)
        values[k].i = std::min(row[k], col[k]), values[k].j = std::max(row[k], col[k]);
    std::sort(values.begin(), values.end(),
              [](const seg_t& s1, const seg_t& s2) {
                  return s1.j < s2.j || (s1.j == s2.j && s1.i < s2.i);
              });
    values.insert(values.begin(), seg_t{-1, -1});
    cover[0][0] = 0;
    for (int squares = 1; squares <= max_sqr; squares++)
        cover[0][squares] = INF;
    int last_idx = -1;
    for (int k = 1, prev_j = -1; k <= n; k++) {
        if (prev_j == values[k].j)
            continue;
        prev_j = values[k].j, last_idx = k;
        cover[k][0] = INF;
        for (int squares = 1; squares <= max_sqr; squares++) {
            cover[k][squares] = INF;
            for (int m = k - 1, left = 0x3f3f3f; m >= 0; m--) {
                left = std::min(left, values[m + 1].i);
                cover[k][squares] = std::min(
                    cover[k][squares],
                    cover[m][squares - 1] + sqr(values[k].j - left + 1)
                            - sqr(std::max(values[m].j - left + 1, 0))
                );
            }
        }
    }
    ll ans = INF;
    for (int squares = 1; squares <= max_sqr; squares++)
        ans = std::min(ans, cover[last_idx][squares]);
    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