Submission #395543

#	Time	Username	Problem	Language	Result	Execution time	Memory
395543		blue	Aliens (IOI16_aliens)	C++17	100 / 100	213 ms	8988 KiB

aliens

#include "aliens.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;

vector<int> R, C;

vector<long long> a(1), b(1);

long long sq(long long x)
{
    return x*x;
}

const long long INF = 1'000'000'000'000'000'001;

struct Line
{
    long long a;
    long long b;
    int photos;
};

deque<Line> CHT;



Line bestLine(long long x) {
    // cerr << "query " << x << '\n';
    // while (CHT.size() >= 2 && intersect(CHT[0], CHT[1]) < x)
    while (CHT.size() >= 2 && CHT[1].b - CHT[0].b < x * (CHT[0].a - CHT[1].a))
        CHT.pop_front();
    return CHT[0];
}

void insert(Line L)
{
    // cerr << "insert L (a=" << L.a << ", b=" << L.b << ")\n";
    while (CHT.size() >= 2)
    {
       Line P = CHT.end()[-1];
       Line Q = CHT.end()[-2];

       if ((Q.b - L.b) * (L.a - P.a) >= (L.a - Q.a) * (P.b - L.b))
       {
          CHT.pop_back();
       }
       else break;
    }
    CHT.push_back(L);
}



long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    R = r;
    C = c;

    int I[n];
    for(int i = 0; i < n; i++)
        I[i] = i;

    sort(I, I+n, [] (int x, int y)
    {
        if(min(R[x], C[x]) == min(R[y], C[y]))
            return max(R[x], C[x]) > max(R[y], C[y]);
        return min(R[x], C[x]) < min(R[y], C[y]);
    });

    int maxb = -1;

    for(int i:I)
    {
        if(maxb < max(r[i], c[i]))
        {
            maxb = max(r[i], c[i]);
            a.push_back(min(r[i], c[i]));
            b.push_back(max(r[i], c[i]));
        }
    }

    n = a.size() - 1;

    k = min(k, n);

    long long low = 0;
    long long high = (long long)m * m;

    a[0] = b[0] = -1;

  long long addition[1 + n];
        for(int j = 0; j <= n; j++)
        {
            addition[j] = -sq(b[j]-a[j+1]+1);
            if (b[j] - a[j+1] + 1 <= 0)
                addition[j] = 0;
        }

    while (low <= high) {
        long long ct = (low + high) / 2;
        long long dp[n+1];
        int photos[n+1];
        CHT.clear();
        // cerr << "----------------------------\n";
        dp[0] = photos[0] = 0;

        for(int i = 0; i <= n; i++)
        {
            // query
            if(i > 0)
            {
                Line L = bestLine(b[i]+1);
                dp[i] = ct + sq(b[i]+1)
                              + L.a * (b[i]+1) + L.b;
                photos[i] = L.photos + 1;
            }


            // update for future queries
            if (i < n) {
                insert(Line{-2*a[i+1],
                            dp[i] + addition[i] + sq(a[i+1]),
                            photos[i]});
            }
        }



       if(low == high) return dp[n] - ct*k;
       else
       {
          if(photos[n] <= k) high = ct;
          else low = ct+1;
       }
    }
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:139:1: warning: control reaches end of non-void function [-Wreturn-type]
  139 | }
      | ^

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