제출 #287254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287254		SamAnd	Aliens (IOI16_aliens)	C++17	16 / 100	126 ms	1372 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 503;

struct ban
{
    int l, r;
};
bool operator<(const ban& a, const ban& b)
{
    return a.r < b.r;
}

int n, m, k;
ban a[N];

int solv1()
{
    bool c[N][N] = {};
    for (int i = 1; i <= n; ++i)
    {
        for (int x = a[i].l; x <= a[i].r; ++x)
        {
            for (int y = a[i].l; y <= a[i].r; ++y)
            {
                c[x][y] = true;
            }
        }
    }
    int ans = 0;
    for (int x = 1; x <= m; ++x)
    {
        for (int y = 1; y <= m; ++y)
        {
            ans += c[x][y];
        }
    }
    return ans;
}

int solv2()
{
    sort(a + 1, a + n + 1);
    int dp[N][N] = {};
    for (int i = 1; i <= n; ++i)
    {
        dp[i][0] = m * m;
        for (int j = 1; j <= k; ++j)
        {
            dp[i][j] = m * m;
            for (int u = i; u >= 1; --u)
            {
                dp[i][j] = min(dp[i][j], dp[u - 1][j - 1] + (a[i].r - a[u].r + 1) * (a[i].r - a[u].r + 1));
            }
        }
    }
    return dp[n][k];
}

int solv3()
{

}

long long take_photos(int n_, int m_, int k_, std::vector<int> r, std::vector<int> c)
{
    n = n_;
    m = m_;
    k = k_;
    for (int i = 1; i <= n; ++i)
    {
        a[i].l = r[i - 1];
        a[i].r = c[i - 1];
        if (a[i].l > a[i].r)
            swap(a[i].l, a[i].r);
        ++a[i].l;
        ++a[i].r;
    }

    vector<ban> v;
    bool z[N] = {};
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (z[j])
                continue;
            if (i == j)
                continue;
            if (a[j].l <= a[i].l && a[i].r <= a[j].r)
            {
                z[i] = true;
                break;
            }
        }
        if (!z[i])
            v.push_back(a[i]);
    }

    n = sz(v);
    for (int i = 1; i <= n; ++i)
        a[i] = v[i - 1];
    k = min(k, n);

    if (n <= 50 && m <= 100 && k == n)
        return solv1();
    return solv2();
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'int solv3()':
aliens.cpp:70:1: warning: no return statement in function returning non-void [-Wreturn-type]
   70 | }
      | ^

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