oj.uz

답안 #828534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828534 2023-08-17T10:50:21 Z caganyanmaz Aliens (IOI16_aliens) C++14
12 / 100
 82 ms 2332 KB 
#include <bits/stdc++.h>

#define pb push_back
#define int int64_t
using namespace std;

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 505;
constexpr static int INF = 1e17;
int dp[MXN][MXN];
long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c)
{
	vector<array<int, 2>> v;
	for (int i = 0; i < n; i++)
	{
		if (c[i] > r[i])
			swap(r[i], c[i]);
		v.pb({c[i], r[i]});
	}
	sort(v.begin(), v.end());
	debug(n, v);
	int last = 0;
	set<int> s;
	s.insert(0);
	for (int i = 1; i < n; i++)
	{
		debug(last, v[last]);
		if (v[last][1] >= v[i][1])
			continue;
		s.insert(i);
		if (v[last][0] == v[i][0] && v[i][1] >= v[last][1])
		{
			debug(last, i, v[last][0], v[i][0]);
			s.erase(last);
		}
		last = i;
	}
	debug(s);
	vector<array<int, 2>> pos;
	for (int nv : s)
		pos.pb(v[nv]);
	debug(pos);
	for (int i = 0; i <= pos.size(); i++)
		for (int j = 0; j <= k; j++)
			dp[i][j] = INF;
	dp[0][0] = 0;
	for (int i = 1; i <= pos.size(); i++)
	{
		for (int j = 1; j <= k; j++)
		{
			for (int l = 0; l < i; l++)
			{
				dp[i][j] = min(dp[i][j], dp[l][j-1] + (1 + pos[i-1][1] - pos[l][0]) * (1 + pos[i-1][1] - pos[l][0]));
				debug(l, i, j, dp[i][j]);
			}
		}
	}
	int best = INF;

	for (int i = 0; i <= k; i++)
	{
		debug(pos.size(), i, dp[pos.size()][i]);
		best = min(best, dp[pos.size()][i]);
	}
	return best;
}

Compilation message

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0; i <= pos.size(); i++)
      |                  ~~^~~~~~~~~~~~~
aliens.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 1; i <= pos.size(); i++)
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
12.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 Correct 1 ms 340 KB Correct answer: answer = 1
4 Correct 1 ms 212 KB Correct answer: answer = 5
5 Correct 1 ms 212 KB Correct answer: answer = 41
6 Correct 0 ms 340 KB Correct answer: answer = 71923
7 Correct 1 ms 980 KB Correct answer: answer = 77137
8 Correct 25 ms 1912 KB Correct answer: answer = 764
9 Correct 1 ms 2260 KB Correct answer: answer = 250000
10 Correct 82 ms 2260 KB Correct answer: answer = 500
11 Correct 0 ms 212 KB Correct answer: answer = 32
12 Correct 1 ms 2260 KB Correct answer: answer = 130050
13 Correct 9 ms 2228 KB Correct answer: answer = 5110
14 Correct 2 ms 1328 KB Correct answer: answer = 2626
15 Correct 4 ms 1236 KB Correct answer: answer = 796
16 Correct 7 ms 2236 KB Correct answer: answer = 7580
17 Correct 23 ms 2224 KB Correct answer: answer = 1904
18 Correct 1 ms 1840 KB Correct answer: answer = 996004
19 Correct 3 ms 1876 KB Correct answer: answer = 38817
20 Correct 13 ms 1900 KB Correct answer: answer = 4096
21 Correct 1 ms 212 KB Correct answer: answer = 1
22 Correct 1 ms 340 KB Correct answer: answer = 1
23 Correct 22 ms 2332 KB Correct answer: answer = 2040
24 Correct 0 ms 340 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 40.0

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