oj.uz

Submission #69257

# Submission time Handle Problem Language Result Execution time Memory
69257 2018-08-20T10:30:24 Z SmsS Aliens (IOI16_aliens) C++14
4 / 100
 93 ms 4716 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define for2(a,b,c) for(int a=b;a < c; a++)
#include "aliens.h"

int dp[510][1010];
int tmp[510][1010];
int R[1010];
int C[1010];

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	if (n > 500) return -1;
	fill(R,R+m+2,(1e9));
	fill(C,C+m+2,(1e9));
	for2(i,0,n){
		R[r[i]]= min(R[r[i]],c[i]);
		C[c[i]]= min(C[c[i]],r[i]);
	}
	for2(i,0,510) for2(j,0,1010){
		if(i <= k) dp[i][j] = 0;
		else dp[i][j] = 1e9;
	}
	for2(i,1,m+1){
		for2(i,0,510) for2(j,0,1010){
			tmp[i][j] = dp[i][j];
			dp[i][j] = (1e9);
		}
		for2(j,0,k+1) for2(t,0,i+1){
			int nt = t;
			nt = min(nt,C[i-1]);
			nt = min(nt,R[i-1]);
			if(j) dp[j][t] = min((ll)dp[j][t],tmp[j-1][nt] + (i-nt)*1ll*(i-nt) - (i-t)*1ll*(i-t) );
			if(nt == t) dp[j][t] = min(dp[j][t],tmp[j][t]);
			if(nt == t && nt == i){
				dp[j][t] = min(dp[j][t],tmp[j][t-1]);
			}
		}
	}
    return dp[k][m];
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Correct answer: answer = 4
2 Correct 7 ms 4456 KB Correct answer: answer = 4
3 Correct 7 ms 4548 KB Correct answer: answer = 4
4 Correct 8 ms 4548 KB Correct answer: answer = 12
5 Correct 12 ms 4552 KB Correct answer: answer = 52
6 Correct 21 ms 4552 KB Correct answer: answer = 210
7 Correct 13 ms 4552 KB Correct answer: answer = 88
8 Correct 85 ms 4620 KB Correct answer: answer = 7696
9 Correct 6 ms 4620 KB Correct answer: answer = 1
10 Correct 46 ms 4620 KB Correct answer: answer = 2374
11 Correct 89 ms 4716 KB Correct answer: answer = 9502
12 Correct 12 ms 4716 KB Correct answer: answer = 49
13 Correct 46 ms 4716 KB Correct answer: answer = 151
14 Correct 85 ms 4716 KB Correct answer: answer = 7550
15 Correct 84 ms 4716 KB Correct answer: answer = 7220
16 Correct 85 ms 4716 KB Correct answer: answer = 7550
17 Correct 87 ms 4716 KB Correct answer: answer = 10000
18 Correct 87 ms 4716 KB Correct answer: answer = 10000
19 Correct 86 ms 4716 KB Correct answer: answer = 624
20 Correct 93 ms 4716 KB Correct answer: answer = 10000

Subtask #2
0 / 12.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Correct answer: answer = 4
2 Correct 7 ms 4456 KB Correct answer: answer = 4
3 Correct 7 ms 4548 KB Correct answer: answer = 4
4 Correct 8 ms 4548 KB Correct answer: answer = 12
5 Correct 12 ms 4552 KB Correct answer: answer = 52
6 Correct 21 ms 4552 KB Correct answer: answer = 210
7 Correct 13 ms 4552 KB Correct answer: answer = 88
8 Correct 85 ms 4620 KB Correct answer: answer = 7696
9 Correct 6 ms 4620 KB Correct answer: answer = 1
10 Correct 46 ms 4620 KB Correct answer: answer = 2374
11 Correct 89 ms 4716 KB Correct answer: answer = 9502
12 Correct 12 ms 4716 KB Correct answer: answer = 49
13 Correct 46 ms 4716 KB Correct answer: answer = 151
14 Correct 85 ms 4716 KB Correct answer: answer = 7550
15 Correct 84 ms 4716 KB Correct answer: answer = 7220
16 Correct 85 ms 4716 KB Correct answer: answer = 7550
17 Correct 87 ms 4716 KB Correct answer: answer = 10000
18 Correct 87 ms 4716 KB Correct answer: answer = 10000
19 Correct 86 ms 4716 KB Correct answer: answer = 624
20 Correct 93 ms 4716 KB Correct answer: answer = 10000
21 Correct 5 ms 4716 KB Correct answer: answer = 1
22 Incorrect 6 ms 4716 KB Wrong answer: output = 1000000000, expected = 4
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Correct answer: answer = 4
2 Correct 7 ms 4456 KB Correct answer: answer = 4
3 Correct 7 ms 4548 KB Correct answer: answer = 4
4 Correct 8 ms 4548 KB Correct answer: answer = 12
5 Correct 12 ms 4552 KB Correct answer: answer = 52
6 Correct 21 ms 4552 KB Correct answer: answer = 210
7 Correct 13 ms 4552 KB Correct answer: answer = 88
8 Correct 85 ms 4620 KB Correct answer: answer = 7696
9 Correct 6 ms 4620 KB Correct answer: answer = 1
10 Correct 46 ms 4620 KB Correct answer: answer = 2374
11 Correct 89 ms 4716 KB Correct answer: answer = 9502
12 Correct 12 ms 4716 KB Correct answer: answer = 49
13 Correct 46 ms 4716 KB Correct answer: answer = 151
14 Correct 85 ms 4716 KB Correct answer: answer = 7550
15 Correct 84 ms 4716 KB Correct answer: answer = 7220
16 Correct 85 ms 4716 KB Correct answer: answer = 7550
17 Correct 87 ms 4716 KB Correct answer: answer = 10000
18 Correct 87 ms 4716 KB Correct answer: answer = 10000
19 Correct 86 ms 4716 KB Correct answer: answer = 624
20 Correct 93 ms 4716 KB Correct answer: answer = 10000
21 Correct 5 ms 4716 KB Correct answer: answer = 1
22 Incorrect 6 ms 4716 KB Wrong answer: output = 1000000000, expected = 4
23 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Correct answer: answer = 4
2 Correct 7 ms 4456 KB Correct answer: answer = 4
3 Correct 7 ms 4548 KB Correct answer: answer = 4
4 Correct 8 ms 4548 KB Correct answer: answer = 12
5 Correct 12 ms 4552 KB Correct answer: answer = 52
6 Correct 21 ms 4552 KB Correct answer: answer = 210
7 Correct 13 ms 4552 KB Correct answer: answer = 88
8 Correct 85 ms 4620 KB Correct answer: answer = 7696
9 Correct 6 ms 4620 KB Correct answer: answer = 1
10 Correct 46 ms 4620 KB Correct answer: answer = 2374
11 Correct 89 ms 4716 KB Correct answer: answer = 9502
12 Correct 12 ms 4716 KB Correct answer: answer = 49
13 Correct 46 ms 4716 KB Correct answer: answer = 151
14 Correct 85 ms 4716 KB Correct answer: answer = 7550
15 Correct 84 ms 4716 KB Correct answer: answer = 7220
16 Correct 85 ms 4716 KB Correct answer: answer = 7550
17 Correct 87 ms 4716 KB Correct answer: answer = 10000
18 Correct 87 ms 4716 KB Correct answer: answer = 10000
19 Correct 86 ms 4716 KB Correct answer: answer = 624
20 Correct 93 ms 4716 KB Correct answer: answer = 10000
21 Correct 5 ms 4716 KB Correct answer: answer = 1
22 Incorrect 6 ms 4716 KB Wrong answer: output = 1000000000, expected = 4
23 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Correct answer: answer = 4
2 Correct 7 ms 4456 KB Correct answer: answer = 4
3 Correct 7 ms 4548 KB Correct answer: answer = 4
4 Correct 8 ms 4548 KB Correct answer: answer = 12
5 Correct 12 ms 4552 KB Correct answer: answer = 52
6 Correct 21 ms 4552 KB Correct answer: answer = 210
7 Correct 13 ms 4552 KB Correct answer: answer = 88
8 Correct 85 ms 4620 KB Correct answer: answer = 7696
9 Correct 6 ms 4620 KB Correct answer: answer = 1
10 Correct 46 ms 4620 KB Correct answer: answer = 2374
11 Correct 89 ms 4716 KB Correct answer: answer = 9502
12 Correct 12 ms 4716 KB Correct answer: answer = 49
13 Correct 46 ms 4716 KB Correct answer: answer = 151
14 Correct 85 ms 4716 KB Correct answer: answer = 7550
15 Correct 84 ms 4716 KB Correct answer: answer = 7220
16 Correct 85 ms 4716 KB Correct answer: answer = 7550
17 Correct 87 ms 4716 KB Correct answer: answer = 10000
18 Correct 87 ms 4716 KB Correct answer: answer = 10000
19 Correct 86 ms 4716 KB Correct answer: answer = 624
20 Correct 93 ms 4716 KB Correct answer: answer = 10000
21 Correct 5 ms 4716 KB Correct answer: answer = 1
22 Incorrect 6 ms 4716 KB Wrong answer: output = 1000000000, expected = 4
23 Halted 0 ms 0 KB -