이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll dp[200005],raod[200005],tana[200005],a[200005],b[200005],n;
struct line {
ll m,c,ind;
ll calc(ll x){
return m * x + c;
}
long double inter(line l){
return (long double)(c - l.c) / (l.m - m);
}
};
deque<line>q;
void insertQ(line x){
while(q.size() >= 2 && q.back().inter(x) <= q.back().inter(q[(int)q.size() - 2]))
q.pop_back();
q.push_back(x);
}
pair<ll,ll> calcQ(ll x){
while(q.size() >= 2 && q[0].calc(x) > q[1].calc(x))
q.pop_front();
return mp(q[0].m * x + q[0].c , q[0].ind);
}
pair<ll,ll>P(ll x){
dp[1] = (b[1] - a[1] + 1) * (b[1] - a[1] + 1) - tana[1] + x;
while(q.size())q.pop_back();
line l;
l.c = a[1] * a[1] - 2 * a[1];
l.m = -2 * a[1];
l.ind = 0;
raod[1] = 1;
insertQ(l);
for(int i=2; i<=n; i++){
pair<ll,ll> p = calcQ(b[i]);
ll mn = p.f + 2 * b[i] + b[i] * b[i] + 1;
ll nex = dp[i - 1] + (b[i] - a[i] + 1) * (b[i] - a[i] + 1);
//cout << nex << '\n';
raod[i] = p.s + 1;
if(nex < mn){
mn = nex;
raod[i] = raod[i - 1] + 1;
}
for(int j=1; j<i; j++){
nex = dp[j - 1] + (b[i] - a[j] + 1) * (b[i] - a[j] + 1);
if(nex < mn){
mn = nex;
raod[i] = raod[j - 1] + 1;
}
}
dp[i] = mn - tana[i] + x;
l.m = -2 * a[i];
l.c = dp[i - 1] + a[i] * a[i] - 2 * a[i];
l.ind = raod[i - 1];
insertQ(l);
}
//cout << x << " " << raod[n] << " " << dp[n] << '\n';
return mp(raod[n] , dp[n]);
}
ll take_photos(int N,int m,int k,vector<int>R,vector<int>C){
n = N;
vector<pair<ll,ll> >w;
ll newn = 0;
for(int i=0; i<n; i++){
if(R[i] > C[i])
swap(R[i] , C[i]);
w.pb(mp(R[i] , -C[i]));
}
sort(w.begin() , w.end());
ll mxc = -1;
for(int i=0; i<w.size(); i++){
if(mxc >= -w[i].s)continue;
else {
newn++;
a[newn] = w[i].f;
b[newn] = -w[i].s;
}
mxc = max(mxc , -w[i].s);
}
n = newn;
/*
// checking all of this
{
cout << n << '\n';
for(int i=1; i<=n; i++){
cout << a[i] << " " << b[i] << '\n';
}
cout << "First Check: Done\n";
}
*/
for(int i=1; i<n; i++)
if(a[i + 1] <= b[i])
tana[i] = (b[i] - a[i + 1] + 1) * (b[i] - a[i + 1] + 1);
ll l = 0,r = m * m ,mid,ans = -1;
while(r >= l){
mid = (l + r) / 2;
pair<ll,ll>got = P(mid);
if(got.f <= k){
r = mid - 1;
if(got.f == min((ll)k , n))return got.s - got.f * mid;
ans = got.s - got.f * mid;
}
else {
l = mid + 1;
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:75:19: 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]
75 | for(int i=0; i<w.size(); i++){
| ~^~~~~~~~~
# | 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... |