Submission #44962

#	Time	Username	Problem	Language	Result	Execution time	Memory
44962		RayaBurong25_1	Aliens (IOI16_aliens)	C++17	0 / 100	2 ms	700 KiB

aliens

#include "aliens.h"
#include <algorithm>
#include <vector>
#include <stdio.h>
typedef struct point point;
struct point
{
    long long r, c;
};
point P[100005];
long long DP[2][100005];
int sortP(point a, point b)
{
    return (a.r < b.r || (a.r == b.r && a.c < b.c));
}
long long min(long long a, long long b)
{
    return (a < b)?a:b;
}
long long max(long long a, long long b)
{
    return (a > b)?a:b;
}
typedef struct line line;
struct line
{
    long long m, c;
    double s;
};
std::vector<line> L;
double intersect(line a, line b)
{
    if (a.m == b.m)
    {
        if (b.c >= a.c)
            return 1e18;
        else
            return -1e18;
    }
    else
        return max(b.s, (double) (a.c - b.c)/(b.m - a.m));
}
void insertLine(line l)
{
    // printf("insertLine %lld %lld\n", l.m, l.c);
    double r;
    while (!L.empty() && (r = intersect(L.back(), l)) <= L.back().s)
        L.pop_back();
    if (r == 1e18)
        return;
    if (L.empty())
    {
        l.s = -1e18;
        L.push_back(l);
    }
    else
    {
        l.s = r;
        L.push_back(l);
    }
}
int compare(line e, long long v)
{
    return e.s < v;
}
long long getLine(long long x)
{
    // int i;
    // for (i = 0; i < L.size(); i++)
        // printf("line %lld %lld %lf\n", L[i].m, L[i].c, L[i].s);
    int j = std::lower_bound(L.begin(), L.end(), x, compare) - L.begin();
    if (j == L.size() || L[j].s > x) j--;
    // printf("getLine x%lld j%d %lld\n", x, j, L[j].m*x + L[j].c);
    return L[j].m*x + L[j].c;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    int i, j;
    long long Ans;
    for (i = 0; i < n; i++)
    {
        P[i].r = min(r[i], c[i]);
        P[i].c = max(r[i], c[i]);
    }
    std::sort(&P[0], &P[n], sortP);
    for (j = 0; j < n; j++)
    {
        DP[1][j] = (P[j].c - P[0].r + 1)*(P[j].c - P[0].r + 1);
        // printf("%lld ", DP[1][j]);
    }
    // printf("\n");
    Ans = DP[1][n - 1];
    for (i = 2; i <= k; i++)
    {
        L.clear();
        L.push_back({0, 1000000000000000000LL, -1e18});
        for (j = 0; j < n; j++)
        {
            // if (j > 0)
                // insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] + (P[j].r - 1)*(P[j].r - 1), -1e18});
            if (j > 0)
                insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] - P[j - 1].c*P[j - 1].c + 2LL*P[j - 1].c*(P[j].r - 1), -1e18});
            DP[i%2][j] = getLine(P[j].c) + P[j].c*P[j].c;
            // printf("%lld ", DP[i%2][j]);
        }
        // printf("\n");
        Ans = min(Ans, DP[i%2][n - 1]);
    }
    return Ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int getLine(long long int)':
aliens.cpp:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j == L.size() || L[j].s > x) j--;
         ~~^~~~~~~~~~~
aliens.cpp: In function 'void insertLine(line)':
aliens.cpp:49:5: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (r == 1e18)
     ^~

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