This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ld long double
const int maxn = 1e5 + 20;
const int maxk = 1e2 + 20;
int l[maxn] , r[maxn];
ll a[maxn] , b[maxn] , dp[maxn] , pd[maxn];
ll t2(int x)
{
return 1LL * x * x;
}
vector<int> hull;
int pt;
ld IS(int i , int j)
{
return (b[i] - b[j]) / (ld)(a[i] - a[j]);
}
void add(int i)
{
a[i] = -2 * l[i + 1];
b[i] = pd[i] + t2(l[i + 1]) - t2(max(0 , r[i] - l[i + 1]));
int sz = hull.size();
while(sz > 1 && IS(hull[sz - 2] , hull[sz - 1]) >= IS(hull[sz - 1] , i))
{
hull.pop_back();
sz--;
}
hull.pb(i);
}
ll f(int ind , int x)
{
return a[ind] * x + b[ind];
}
ll get(int x)
{
pt = 0;
while(pt + 1 < (int)hull.size() && f(hull[pt] , x) >= f(hull[pt + 1] , x))
pt++;
return f(hull[pt] , x);
}
long long take_photos(int n, int m, int k, vector<int> R, vector<int> C)
{
m = m;
vector<pair<int , int> > tmp;
for(int i = 0; i < n; i++)
{
l[i] = min(R[i] , C[i]) , r[i] = max(R[i] , C[i]);
tmp.pb({r[i] , -l[i]});
}
sort(tmp.begin() , tmp.end());
for(int i = 0; i < n; i++)
{
l[i] = -tmp[i].second;
r[i] = tmp[i].first;
}
tmp.clear();
int mn = 1e9;
for(int i = n - 1; i >= 0; i--)
if(mn > l[i])
{
mn = l[i];
tmp.pb({l[i] , r[i]});
}
reverse(tmp.begin() , tmp.end());
n = tmp.size();
for(int i = 1; i <= n; i++)
l[i] = tmp[i - 1].first , r[i] = tmp[i - 1].second + 1;
r[0] = l[0] = -1;
memset(dp , 63 , sizeof dp);
dp[0] = 0;
for(int j = 1; j <= k; j++)
{
hull.clear();
pt = 0;
memcpy(pd , dp , sizeof dp);
memset(dp , 63 , sizeof dp);
dp[0] = 0;
for(int i = 1; i <= n; i++)
{
add(i - 1);
for(int k = 0; k < i; k++)
dp[i] = min(dp[i] , a[k] * r[i] + b[k] + t2(r[i]));
}
}
return dp[n];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |