oj.uz

답안 #612712

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612712 2022-07-29T21:30:49 Z Apiram Aliens (IOI16_aliens) C++14
0 / 100
 1 ms 212 KB 
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	 vector<vector<long long>>arr(m + 1);
    for (long long i = 0;i<n;++i){
		 r[i]--;
		 c[i]--;
		 if (c[i] > r[i])swap(r[i],c[i]);
		 long long temp = (r[i] - c[i]);
		 if (temp % 2 == 1){
			 long long row = temp;
			 long long col = m - temp;
			 long long dist = max(abs(r[i] - row),abs(c[i] - col));
			 arr[temp].push_back(dist - 1); 
		 }
		 else{
			 long long row = temp - 1;
			 long long col = m - row;
			 long long dist = max(abs(r[i] - row),abs(c[i] - col));
			 if (dist - 1 <= temp - 1)
				arr[temp - 1].push_back(dist - 1);
			 row = temp + 1;
			 col = m - row;
			 dist = max(abs(r[i] - row),abs(c[i] - col));
			 if (dist - 1 <= temp + 1){
				arr[temp + 1].push_back(dist - 1);
			 }
		 }
	 }
	 for (long long i = 0;i<=m;++i)sort(arr[i].begin(),arr[i].end());
	 vector<pair<long long,long long>>dp(m + 1,{0,0}); 
	 for (long long i = 0;i<m;++i){
		long long dist = 0;
		if (!arr[i].empty()){
			dist = arr[i].back();
		}
		auto temp = dp[i - dist];
		long long p = (long long)arr[i].size();
		long long total = dist * dist * 4;
		if (dp[i + dist].first < p + temp.first){
			dp[i + dist].first = p + temp.first;
			dp[i + dist].second = total + temp.second;
		}
		else if (dp[i + dist].first == p + temp.first && dp[i + dist].second > temp.second + total){
			dp[i + dist].first = p + temp.first;
			dp[i + dist].second = total + temp.second;
		}
	 }
	 long long ans = m * m;
	 for (long long i = 0;i<=m;++i){
		if (dp[i].first == n){
			ans = min(ans,dp[i].second);
		}
	 }
	 return ans;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 40.0

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