Submission #1067521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067521		andrei_iorgulescu	Aliens (IOI16_aliens)	C++14	41 / 100	2019 ms	3728 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#warning That's not FB, that's my FB

using namespace std;

using ll = long long;
using ld = long double;

const ld eps = 0.00000001d;

int n, m;
vector<int> l, r;

bool cmp(pair<int,int> A, pair<int,int> B)
{
    if (A.first != B.first)
        return A.first < B.first;
    return A.second > B.second;
}

void norma_intvs()
{
    vector<pair<int,int>> vp;
    for (int i = 0; i < l.size(); i++)
        vp.push_back({l[i], r[i]});
    sort(vp.begin(), vp.end(), cmp);
    l.clear();
    r.clear();
    int rmax = -1;
    for (auto it : vp)
    {
        if (it.second > rmax)
        {
            rmax = it.second;
            l.push_back(it.first);
            r.push_back(it.second);
        }
    }
}

struct ura
{
    ld val;
    int cate;
};

ura dp[200005];

void solve(ld cost)
{
    dp[0].val = dp[0].cate = 0;
    for (int i = 1; i <= n; i++)
    {
        ld vl_min = 10000000000000000;
        int cn;
        for (int q = 1; q <= i; q++)
        {
            ld cur_vl = cost + dp[q - 1].val + (ld)(r[i] - l[q] + 1) * (ld)(r[i] - l[q] + 1);
            if (q != 1 and l[q] <= r[q - 1])
                cur_vl -= (ld)(r[q - 1] - l[q] + 1) * (ld)(r[q - 1] - l[q] + 1);
            if (cur_vl < vl_min)
            {
                vl_min = cur_vl;
                cn = q;
            }
        }
        dp[i].val = vl_min;
        dp[i].cate = 1 + dp[cn - 1].cate;
    }
}

ll take_photos(int N, int M, int k, vector<int> R, vector<int> C)
{
    n = N, m = M;
    for (int i = 0; i < n; i++)
    {
        l.push_back(min(R[i],C[i]));
        r.push_back(max(R[i],C[i]));
    }
    norma_intvs();
    n = l.size();
    vector<int> newl = {0};
    for (auto it : l)
        newl.push_back(it);
    l = newl;
    vector<int> newr = {0};
    for (auto it : r)
        newr.push_back(it);
    r = newr;
    ld st = (ll)1e6 * (ll)1e6;
    ld pas = 1ll << 39;
    while (pas >= eps)
    {
        if (st - pas >= 0)
        {
            solve(st - pas);
            if (dp[n].cate <= k)
                st -= pas;
        }
        pas /= 2.0d;
    }
    solve(st);
    ld ans = dp[n].val - st * (ld)k;
    if (ans - (ll)ans <= 0.5d)
        return (ll)ans;
    return (ll)ans + 1;
}

Compilation message (stderr)

aliens.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
aliens.cpp: In function 'void norma_intvs()':
aliens.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
aliens.cpp: In function 'void solve(ld)':
aliens.cpp:69:32: warning: 'cn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |         dp[i].cate = 1 + dp[cn - 1].cate;
      |                             ~~~^~~

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