Submission #361509

#	Time	Username	Problem	Language	Result	Execution time	Memory
361509		ryangohca	Aliens (IOI16_aliens)	C++17	100 / 100	394 ms	9180 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long, long long>
vector<pii> points;
vector<pii> impt;
pii dp[100001];
deque<pair<pii, int>> dq;
long long f(pii line, long long x){
     return line.first*x + line.second;
}
pii query(long long x){
    while(dq.size()>1){ //to prevent seg fault when accessing dq[1]
        long long fa = f(dq[0].first, x), fb = f(dq[1].first, x);
        if (fa == fb){
            if (dq[0].second > dq[1].second) dq.pop_front();
            else break;
        } else if(fa > fb) //the next line is better
            dq.pop_front(); //remove useless line
        else break;
    }
    return pii(f(dq[0].first,x), dq[0].second);
}
double intersect(long long m1, long long c1, long long m2, long long c2){
      return (double)(c2-c1)/(m1-m2);
}
double intersect(pii p1, pii p2){
      return intersect(p1.first,p1.second,p2.first,p2.second);
}
void insert(long long m,long long c, long long x) {//insert line y=mx+c
     pii line = make_pair(m,c);
     while (dq.size()>1) { //to prevent seg fault
         int s = dq.size();
         double a = intersect(dq[s-1].first, line), b = intersect(dq[s-2].first, line);
         if (a <= b) dq.pop_back(); //removes useless line
         else break;
     }
     dq.push_back({line, x});
}
long long sq(long long x){
    return x*x;
}
pii check(long long c){
    dq.clear();
    dp[0] = {0, 0};
    for (int i = 1; i < impt.size(); i++){
        dp[i] = {sq(impt[i].second - impt[1].first + 1) + c, 1};
        if (i != 1) {
            insert(-2 * impt[i].first, sq(impt[i].first) - 2 * (impt[i].first) + dp[i-1].first - sq(max(0ll, impt[i-1].second - impt[i].first + 1)), dp[i-1].second);
            pii g = query(impt[i].second);
            g.first += sq(impt[i].second) + 2 * impt[i].second + c + 1;
            g.second++;
            dp[i] = min(dp[i], g);
        }
        /*
        for (int j = 2; j <= i; j++){
            dp[i] = min(dp[i], {dp[j-1].first + c + sq(impt[i].second - impt[j].first + 1) - sq(max(0ll, impt[j-1].second - impt[j].first + 1)), dp[j-1].second + 1});
        }
        */
    }
    return dp[impt.size()-1];
}
// sq(impt[i].second - impt[j].first + 1)
// = dp[j-1].first + c + -2 * (impt[i].second) * (impt[j].first) + impt[i].second ^ 2 + 2 * impt[i].second + impt[j].first ^ 2 - 2 * (impt[j].first) + 1
// = [-2 * (impt[i].second) * (impt[j].first) + impt[j].first ^ 2 - 2 * (impt[j].first) + dp[j-1].first] + impt[i].second ^ 2 + 2 * impt[i].second + c + 1
long long take_photos(int N, int m, int K, std::vector<int> R, std::vector<int> C) {
   for (int i = 0; i < N; i++) {
       int r = R[i], c = C[i];
       if (r > c) swap(r, c);
       points.push_back({r, c});
   }
   impt.push_back({-1, -1}); // dummy
   sort(points.begin(), points.end());
   for (auto [a, b] : points){
       if (impt.empty() || impt.back().second < b) impt.push_back({a, b}); 
   }
   //K = min(K, (int)impt.size()-1);
   long long mini = -1, maxi = 1e16;
   while (maxi - mini > 1){
       long long mid = (maxi + mini) /2;
       if (check(mid).second <= K) maxi = mid;
       else mini = mid;
   }
   return check(maxi).first - K * maxi;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, long long int> check(long long int)':
aliens.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 1; i < impt.size(); i++){
      |                     ~~^~~~~~~~~~~~~

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