oj.uz

Submission #24564

# Submission time Handle Problem Language Result Execution time Memory
24564 2017-06-10T12:53:53 Z Jeyeon Si(#1045) Aliens (IOI16_aliens) C++
12 / 100
 209 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=0;k<=l;k++) dyn[0][k] = 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],0LL)*max(e[j]-s[j+1]+1,0LL));
		}
	}

    return dyn[n][l];
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Correct answer: answer = 4
2 Correct 0 ms 6312 KB Correct answer: answer = 4
3 Correct 0 ms 6312 KB Correct answer: answer = 4
4 Incorrect 0 ms 6312 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Correct answer: answer = 1
2 Correct 0 ms 6312 KB Correct answer: answer = 4
3 Correct 0 ms 6312 KB Correct answer: answer = 1
4 Correct 0 ms 6312 KB Correct answer: answer = 5
5 Correct 0 ms 6312 KB Correct answer: answer = 41
6 Correct 0 ms 6312 KB Correct answer: answer = 71923
7 Correct 0 ms 6312 KB Correct answer: answer = 77137
8 Correct 63 ms 6312 KB Correct answer: answer = 764
9 Correct 0 ms 6312 KB Correct answer: answer = 250000
10 Correct 209 ms 6312 KB Correct answer: answer = 500
11 Correct 0 ms 6312 KB Correct answer: answer = 32
12 Correct 0 ms 6312 KB Correct answer: answer = 130050
13 Correct 19 ms 6312 KB Correct answer: answer = 5110
14 Correct 0 ms 6312 KB Correct answer: answer = 2626
15 Correct 9 ms 6312 KB Correct answer: answer = 796
16 Correct 16 ms 6312 KB Correct answer: answer = 7580
17 Correct 56 ms 6312 KB Correct answer: answer = 1904
18 Correct 0 ms 6312 KB Correct answer: answer = 996004
19 Correct 6 ms 6312 KB Correct answer: answer = 38817
20 Correct 26 ms 6312 KB Correct answer: answer = 4096
21 Correct 0 ms 6312 KB Correct answer: answer = 1
22 Correct 0 ms 6312 KB Correct answer: answer = 1
23 Correct 56 ms 6312 KB Correct answer: answer = 2040
24 Correct 0 ms 6312 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Correct answer: answer = 4
2 Correct 0 ms 6312 KB Correct answer: answer = 4
3 Correct 0 ms 6312 KB Correct answer: answer = 4
4 Incorrect 0 ms 6312 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Correct answer: answer = 4
2 Correct 0 ms 6312 KB Correct answer: answer = 4
3 Correct 0 ms 6312 KB Correct answer: answer = 4
4 Incorrect 0 ms 6312 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Correct answer: answer = 4
2 Correct 0 ms 6312 KB Correct answer: answer = 4
3 Correct 0 ms 6312 KB Correct answer: answer = 4
4 Incorrect 0 ms 6312 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Correct answer: answer = 4
2 Correct 0 ms 6312 KB Correct answer: answer = 4
3 Correct 0 ms 6312 KB Correct answer: answer = 4
4 Incorrect 0 ms 6312 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -