oj.uz

답안 #24569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24569 2017-06-10T13:06:07 Z Jeyeon Si(#1045) Aliens (IOI16_aliens) C++
0 / 100
 0 ms 6312 KB 
#include "aliens.h"
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int n, m, l;
ll dyn[600][600];
vector<pii> lis;
ll s[100100], e[100100];

inline bool cmp(pii a, pii b) {return a.first<b.first||(a.first==b.first&&a.second>b.second);}

ll take_photos(int N, int M, int L, vector<int> r, vector<int> c) {
	n=N;m=M;l=L;
	int i, j, k, p = 0, maxi = -1;
	for (i=0;i<n;i++) lis.push_back(pii(min(r[i],c[i]),max(r[i],c[i])));
	sort(lis.begin(),lis.end(),cmp);
	for (i=0;i<n;i++) {
		if (maxi<lis[i].second) lis[p++] = lis[i];
		maxi = max(maxi,lis[i].second);
	}
	lis.erase(lis.begin()+p,lis.end());
	n = p;
	for (i=1;i<=n;i++) s[i] = lis[i-1].first, e[i] = lis[i-1].second;
	for (i=1;i<=n;i++) dyn[i][0] = 1LL<<52;
	for (k=1;k<=l;k++) dyn[0][k] = 1LL<<52;
	dyn[0][0] = 0;
	for (k=1;k<=l;k++) {
		for (i=1;i<=n;i++) {
			dyn[i][k] = 1LL<<52;
			for (j=0;j<i;j++) dyn[i][k] = min(dyn[i][k],dyn[j][k-1]+(e[i]-s[j+1]+1)*(e[i]-s[j+1]+1)-max(e[j]-s[j+1]+1,0LL)*max(e[j]-s[j+1]+1,0LL));
		}
	}

	ll res = 1LL<<52;
	for (i=1;i<=l;i++) res = min(res,dyn[n][i]);
    return res;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 6312 KB Wrong answer: output = 3, expected = 4
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 6312 KB Wrong answer: output = 0, expected = 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 6312 KB Wrong answer: output = 3, expected = 4
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 6312 KB Wrong answer: output = 3, expected = 4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 6312 KB Wrong answer: output = 3, expected = 4
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 6312 KB Wrong answer: output = 3, expected = 4
2 Halted 0 ms 0 KB -