이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ent '\n'
#define line pair<ll, ll>
#define k first
#define b second
typedef long long ll;
using namespace std;
const int maxn = 1e6+12;
vector<int> g[maxn];
bool was[maxn];
ll dp[maxn];
ll ndp[maxn];
int L[maxn];
int R[maxn];
bool check(line nw, line last, line prl){
if((nw.b - prl.b) * (prl.k - last.k) <= (last.b - prl.b) * (prl.k - nw.k))return 1;
return 0;
}
int ptr = 0;
vector<line> l;
void add(line x){
while(l.size() && l.back().k == x.k && l.back().b > x.b){
l.pop_back();
}
if(l.size() && l.back().k == x.k && l.back().b <= x.b){
return;
}
while(l.size()>1 && check(x, l.back(), l[l.size()-2])){
l.pop_back();
}
l.push_back(x);
}
ll get(ll x){
if(!l.size()){
return 1e12+1;
}
if(ptr >= l.size()){
ptr = l.size()-1;
}
while(ptr + 1 < l.size() && l[ptr].k * x + l[ptr].b > l[ptr+1].k * x + l[ptr+1].b){
ptr++;
}
return l[ptr].k * x + l[ptr].b;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){
for(int i=1;i<=m;i++){
L[i] = 1e9;
}
m = 0;
for(int i=0;i<n;i++){
if(r[i] < c[i]){
swap(r[i], c[i]);
}
r[i]++, c[i]++;
L[r[i]] = min(L[r[i]], c[i]);
R[c[i]] = max(R[c[i]], r[i]);
for(int x=-1;x<=0;x++){
was[r[i]+x] = was[c[i]+x] = 1;
}
m = max(m, r[i]);
}
was[1] = 1;
vector<int> t;
for(int i=1;i<=m;i++){
dp[i] = ndp[i] = 1e12+1;
R[i] = max(R[i], R[i-1]);
if(!was[i]) continue;
t.push_back(i);
g[max(R[i], i)].push_back(i);
}
for(int _=1;_<=k;_++){
add({0, 0});
for(int &i:t){
ndp[i] = get(i) + i * 1ll * i;
for(int &j:g[i]){
ll b = j * 1ll * j + dp[R[j]];
if(R[j] > j) b -= (R[j] - j) * 1ll * (R[j] - j);
add(line(-2 * j, b));
}
}
for(int &i:t){
dp[i] = ndp[i];
}
ptr = 0;
l.clear();
}
return dp[m];
}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'll get(ll)':
aliens.cpp:41:16: 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]
41 | if(ptr >= l.size()){
| ~~~~^~~~~~~~~~~
aliens.cpp:44: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]
44 | while(ptr + 1 < l.size() && l[ptr].k * x + l[ptr].b > l[ptr+1].k * x + l[ptr+1].b){
| ~~~~~~~~^~~~~~~~~~
# | 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... |