제출 #274779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274779		stoyan_malinin	Aliens (IOI16_aliens)	C++14	4 / 100	80 ms	2816 KiB

aliens

#include "aliens.h"
//#include "grader.cpp"

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 4005, MAXK = 105;

struct Point
{
    int r, c;

    Point(){}
    Point(int r, int c)
    {
        this->r = r;
        this->c = c;
    }
};

bool cmpCol(Point A, Point B)
{
    if(A.c!=B.c) return A.c<B.c;
    return A.r>B.r;
}

int n, m, k;

int opt[MAXN][MAXK];
long long dp[MAXN][MAXK];

vector <Point> v;
int squareSz[MAXN][MAXN], leftestCover[MAXN][MAXN];

void init()
{
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<=k;j++)
        {
            dp[i][j] = 6969696966969LL;
        }
    }

    vector <bool> toRemove;
    toRemove.assign(v.size(), false);

    for(int i = 0;i<n;i++)
    {
        int d = v[i].c - v[i].r + 1;
        for(int j = 0;j<i;j++)
        {
            if(v[i].c-v[j].c<d && abs(v[i].c-v[j].r)<d)
            {
                toRemove[j] = true;
            }
        }
    }

    vector <Point> newV;
    for(int i = 0;i<v.size();i++)
    {
        if(toRemove[i]==false) newV.push_back(v[i]);
    }

    v = newV;
    n = v.size();

    for(int r = 0;r<v.size();r++)
    {
        //cout << v[r].r << " --- " << v[r].c << '\n';

        int maxDist = -1;
        for(int l = r;l>=0;l--)
        {
            maxDist = max(maxDist, (v[l].c-v[l].r)+(v[r].c-v[l].c));
            squareSz[l][r] = maxDist + 1;
        }
    }

    //cout << "->" << leftestCover[1][4] << '\n';
}

long long squareNum(long long x)
{
    if(x<0) return 0;
    return x*x;
}

void evalDP(int l, int r, int lOpt, int rOpt, int j)
{
    if(l>r) return;

    //int mid = (l+r)/2;

    //cout << mid << " -> " << lOpt << " " << rOpt << '\n';
    for(int mid = l;mid<=r;mid++)
    {
        for(int p = 0;p<=mid;p++)
        {
            long long curr;
            if(p!=0) curr = dp[p-1][j-1] + squareNum(squareSz[p][mid])
                            - squareNum(v[p-1].c-(v[mid].c-squareSz[p][mid]));
            else
                curr = squareNum(squareSz[p][mid]);

            if(dp[mid][j]>curr)
            {
                opt[mid][j] = p;
                dp[mid][j] = curr;
            }
            //cout << p << " -> " << squareNum(v[p-1].c-(v[i].c-squareSz[p][i])) << " " << side << '\n';
        }
    }


    //evalDP(l, mid-1, lOpt, rOpt, j);
    //evalDP(mid+1, r, lOpt, rOpt, j);
}

long long take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c)
{
    n = _n;
    m = _m;
    k = _k;

    for(int i = 0;i<n;i++)
    {
        if(c[i]<r[i]) swap(c[i], r[i]);
    }

    for(int i = 0;i<n;i++) v.push_back(Point(r[i], c[i]));
    sort(v.begin(), v.end(), cmpCol);

    init();
    for(int i = 0;i<n;i++) dp[i][0] = squareNum(squareSz[0][i]);
    for(int j = 1;j<k;j++)
    {
        evalDP(0, n-1, 0, n-1, j);
    }

    long long answer = 6996969969696996LL;
    for(int i = 0;i<k;i++) answer = min(answer, dp[n-1][i]);

    return answer;
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6

5 10 2
0 3
3 4
4 3
3 3
4 2
*/

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

aliens.cpp: In function 'void init()':
aliens.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0;i<v.size();i++)
      |                   ~^~~~~~~~~
aliens.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int r = 0;r<v.size();r++)
      |                   ~^~~~~~~~~

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