이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
int x,y;
}a[1000005];
long long int dp[50005][105],x[100005],y[100005];
bool cmp(node a,node b)
{
if(a.x<b.x)return 1;
if(a.x>b.x)return 0;
if(a.y<a.y)return 1;
return 0;
}
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++)
{
a[i].x=r[i];
a[i].y=c[i];
if(a[i].y<a[i].x)
{
swap(a[i].x,a[i].y);
}
}
sort(a,a+n,cmp);
long long int cnt=1;
x[1]=a[0].x;
y[1]=a[0].y;
for(int i=1;i<n;i++)
{
if(a[i].x>x[cnt] && a[i].y>=y[cnt])
{
cnt++;
x[cnt]=a[i].x;
y[cnt]=a[i].y;
}
else if(a[i].x==x[cnt] && a[i].y>y[cnt])
{
x[cnt]=a[i].x;
y[cnt]=a[i].y;
}
}
n=cnt;
x[0]=-1;
y[0]=-1;
for(int i=1;i<=n;i++)
{
//cout<<x[i]<<" "<<y[i]<<endl;
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=k;j++)dp[i][j]=99999999999999999;
}
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
long long int nowy=y[i],nowx=x[i];
for(int l=i;l>=1;l--)
{
nowx=x[l];
if(y[l-1]-x[l]+1>0)dp[i][j]=min(dp[i][j],dp[l-1][j-1]+(nowy-nowx+1)*(nowy-nowx+1)-(y[l-1]-x[l]+1)*(y[l-1]-x[l]+1));
else dp[i][j]=min(dp[i][j],dp[l-1][j-1]+(nowy-nowx+1)*(nowy-nowx+1));
//cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<dp[l-1][j-1]<<" "<<nowx<<" "<<nowy<<endl;
}
}
}
long long int ans=10000000000000;
for(int i=0;i<=k;i++)
{
ans=min(dp[n][i],ans);
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'bool cmp(node, node)':
aliens.cpp:13:8: warning: self-comparison always evaluates to false [-Wtautological-compare]
if(a.y<a.y)return 1;
~~~^~~~
# | 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... |