Submission #1175024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175024		totoro	Aliens (IOI16_aliens)	C++17	4 / 100	0 ms	328 KiB

aliens

// SOLVED SUBTASK 1   (04 pts)
// SOLVED SUBTASK 2   (12 pts)
// SOLVED SUBTASK 3   (09 pts)
// UNSOLVED SUBTASK 4 (16 pts)
// UNSOLVED SUBTASK 5 (19 pts)
// UNSOLVED SUBTASK 6 (40 pts)
// [+-+]----------------------
// TOTAL     25/100 pts

#include "aliens.h"

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

struct Coordinate {
    long long row, col;
    Coordinate(long long row, long long col) : row(std::min(row, col)), col(std::max(row, col)) {}
    bool operator<(const Coordinate& other) const {
        if (row == other.row) {
            return col > other.col;
        }
        return row < other.row;
    }
};

struct Range {
    long long start, end;
    Range(long long start, long long end) : start(start), end(end) {};
    long long merge(const Range& other) const {
        return 2 * (other.start - start) * (other.end - end) - (other.start > end ? (other.start - end - 1) * (other.start - end - 1) : 0);
    }
};

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    std::vector<Coordinate> points;
    for (size_t i = 0; i < n; ++i) {
        points.push_back(Coordinate(r[i], c[i]));
    }
    std::sort(points.begin(), points.end());

    std::vector<Range> ranges;
    long long furthestStart = -1;
    long long furthestEnd = -1;
    for (size_t i = 0; i < points.size(); ++i) {
        Coordinate point = points[i];
        if (point.row > furthestStart && point.col > furthestEnd) {
            ranges.emplace_back(point.row, point.col);
            furthestStart = point.row;
            furthestEnd = point.col;
        }
    }

    std::vector<std::vector<long long>> dp;
    for (size_t range = 0; range < ranges.size(); ++range) {
        dp.emplace_back();
        for (size_t coverCount = 1; coverCount <= k; ++coverCount) {
            if (coverCount == 1 || range == 0) {
                dp[range].push_back((ranges[range].end - ranges[0].start + 1) * (ranges[range].end - ranges[0].start + 1));
                continue;
            }

            // ternary search
            int lo = 0, hi = range - 1;
            while (lo < hi) {
                int m1 = lo + (hi - lo) / 3;
                int m2 = hi - (hi - lo) / 3;
                long long score1 = dp[m1][coverCount - 2] + (ranges[range].end - ranges[m1 + 1].start + 1) * (ranges[range].end - ranges[m1 + 1].start + 1);
                if (ranges[m1 + 1].start <= ranges[m1].end) {
                    score1 -= (ranges[m1].end - ranges[m1 + 1].start + 1) * (ranges[m1].end - ranges[m1 + 1].start + 1);
                }
                long long score2 = dp[m2][coverCount - 2] + (ranges[range].end - ranges[m2 + 1].start + 1) * (ranges[range].end - ranges[m2 + 1].start + 1);
                if (ranges[m2 + 1].start <= ranges[m2].end) {
                    score2 -= (ranges[m2].end - ranges[m2 + 1].start + 1) * (ranges[m2].end - ranges[m2 + 1].start + 1);
                }
                if (score1 < score2) {
                    hi = m1;
                } else if (score1 > score2) {
                    lo = m2;
                } else {
                    hi = m2 - 1;
                    lo = m1;
                }
            }
            long long score = dp[lo][coverCount - 2] + (ranges[range].end - ranges[lo + 1].start + 1) * (ranges[range].end - ranges[lo + 1].start + 1);
            if (ranges[lo + 1].start <= ranges[lo].end) {
                score -= (ranges[lo].end - ranges[lo + 1].start + 1) * (ranges[lo].end - ranges[lo + 1].start + 1);
            }
            dp[range].push_back(score);
        }
    }

    return dp[ranges.size() - 1][k - 1];
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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