Submission #395486

#	Time	Username	Problem	Language	Result	Execution time	Memory
395486		blue	Aliens (IOI16_aliens)	C++17	41 / 100	2095 ms	3612 KiB

aliens

#include "aliens.h"
#include <vector>
#include <algorithm>
#include <iostream>
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;
 
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];
        dp[0] = photos[0] = 0;
 
        for(int i = 1; i <= n; i++)
        {
            dp[i] = INF;
            photos[i] = i+1;
            for(int j = 0; j < i; j++)
            {
                long long val = ct + dp[j] + addition[j]
                              + sq(b[i]+1) - 2 * (b[i]+1) * a[j+1] + sq(a[j+1]);
                
                if(val < dp[i])
                {
                    photos[i] = photos[j] + 1;
                    dp[i] = val;
                }
            }
        }
 
 
 
       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:96:1: warning: control reaches end of non-void function [-Wreturn-type]
   96 | }
      | ^

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