Submission #787365

#	Time	Username	Problem	Language	Result	Execution time	Memory
787365		LuoBo	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN=10010;
struct node {
	int x, y;
} t[MAXN], p[MAXN];
long long f[MAXN][MAXN];
 
bool cmp(node x, node y) { return x.x==y.x ? x.y<y.y : x.x<y.x ; }
long long sq(long long x) { return x*x; }
bool tan_judge(node x, node y, node z) { return ( (double)( z.y-y.y ) / (double)( z.x-y.x ) > (double)( y.y-x.y ) / (double)( y.x-x.x ) ) ? 1 : 0 ; }
 
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	
	for (int i=0; i<n; i++) {
		t[i].x=r[i]; t[i].y=c[i];
		if ( r[i]>c[i] ) swap(t[i].x,t[i].y); 
	}
	sort(t, t+n, cmp);
	
	int right=-1, tt=0;
	p[0].x=-1; p[0].y=-1;
	for (int i=0; i<n; i++) {
		if ( t[i].y<=right ) continue;
		right=t[i].y; p[++tt]=t[i];
	}
	n=tt;
	
//	printf("step1:\n");	for (int i=1;i<=n;i++) printf("%d %d\n",p[i].x,p[i].y);
	
	tt=0;
	for (int i=1; i<=n; i++) {
		if ( tt<=2 ) { t[++tt]=p[i]; continue; }
		if ( tan_judge(p[i], t[tt], t[tt-1]) ) t[++tt]=p[i];
		else {
			while ( tt>2 && !tan_judge(p[i], t[tt], t[tt-1]) ) tt--;
			t[++tt]=p[i];
		}
	}
 	n=tt;
 	
//	printf("step2:\n"); for (int i=1;i<=n;i++) printf("%d %d\n",t[i].x,t[i].y);
 
	long long ans=1e10;
	for (int i=0;i<=n;i++)
		for (int opt=0;opt<=k;opt++) f[i][opt]=1e10;
	f[0][0]=0;
	
//	for (int i=1; i<=n; i++) {
//		for (int opt=1; opt<=k; opt++) {
//			for (int j=0; j<i; j++) {
//				f[i][opt]=min(f[i][opt], f[j][opt-1] + sq( p[i].y-p[j+1].x+1 ) - sq( max(0, p[j].y-p[j+1].x+1) ) );
//			}
//		}
//	}
	
	for (int i=1; i<=n; i++) {
		for (int opt=1; opt<=k; opt++) {
			for (int j=0; j<i; j++) {
				f[i][opt]=min(f[i][opt], f[j][opt-1] + sq( t[j+1].x ) - sq( max(0, t[j].y-t[j+1].x+1) ) + sq( t[i].y ) + 2*t[i].x + 2*t[i].y + 1 - 2*t[i].x*t[j].y );
			}
		}
	}
	
	for (int opt=1;opt<=k;opt++) ans=min(ans,f[n][opt]);
	return ans;
	
}
 
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/

int main() {
	
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &r[i], &c[i]);
    }
    long long ans = take_photos(n, m, k, r, c);
    
    
    printf("%lld\n", ans);
    
    return 0;
}

Compilation message (stderr)

aliens.cpp: In function 'int main()':
aliens.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%d %d", &r[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cclNZYpX.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccm3rwaW.o:aliens.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status