이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;
vector <pll> line;
double cross(pll a, pll b) {return (double)(b.se - a.se) / (a.fi - b.fi);}
void add_line(pll l) {
while(line.size() >= 2) {
pll l1 = line[line.size()-2], l2 = line[line.size()-1];
if(cross(l1, l2) < cross(l2, l)) break;
line.pop_back();
}
line.eb(l);
}
//solution for nk log n
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector <pii> tarr, arr;
vector < vector <ll> > dp;
dp.resize(k+3);
for(int i = 0; i < n; i++) {
if(r[i] < c[i]) swap(r[i], c[i]);
r[i]++;
tarr.eb(r[i], c[i]);
}
sort(all(tarr));
arr.eb(0, -1);
for(int i = 0; i < n; i++) {
while(!arr.empty() && arr.back().se >= tarr[i].se) arr.pop_back();
arr.eb(tarr[i]);
}
n = arr.size() - 1;
k = min(n, k);
dp[1].resize(n+1);
for(int i = 1; i <= n; i++) dp[1][i] = (arr[i].fi - arr[1].se) * (arr[i].fi - arr[1].se);
for(int i = 2; i <= k; i++) {
dp[i].resize(n+1);
int idx = 0;
while(!line.empty()) line.pop_back();
add_line(make_pair(-2*arr[1].se, arr[1].se * arr[1].se));
for(int j = 1; j <= n; j++) {
while(idx + 1 < line.size() && cross(line[idx], line[idx+1]) <= (double)arr[j].fi) idx++;
dp[i][j] = arr[j].fi * arr[j].fi + line[idx].fi * arr[j].fi + line[idx].se;
if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se)));
}
}
return dp[k][n];
}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(idx + 1 < line.size() && cross(line[idx], line[idx+1]) <= (double)arr[j].fi) idx++;
~~~~~~~~^~~~~~~~~~~~~
# | 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... |