oj.uz

Submission #349199

# Submission time Handle Problem Language Result Execution time Memory
349199 2021-01-17T04:14:06 Z arnold518 Fence (CEOI08_fence) C++14
100 / 100
 443 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 100;

struct Point
{
	int x, y;
};

Point operator + (Point p, Point q) { return {p.x+q.x, p.y+q.y}; }
Point operator - (Point p, Point q) { return {p.x-q.x, p.y-q.y}; }
ll ccw(Point p, Point q) { return p.x*q.y-p.y*q.x; }

int N, M;
Point A[MAXN+10], B[MAXN+10];
int C[MAXN+10][MAXN+10];

int dp[MAXN+10], ans=0;

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y);
	for(int i=1; i<=M; i++) scanf("%d%d", &B[i].x, &B[i].y);

	for(int i=1; i<=N; i++)
	{
		vector<int> V;
		for(int j=1; j<=N; j++)
		{
			if(A[i].y<A[j].y || (A[i].y==A[j].y && A[i].x<A[j].x)) V.push_back(j);
		}

		sort(V.begin(), V.end(), [&](const int &p, const int &q)
		{
			return ccw(A[p]-A[i], A[q]-A[i])>0;
		});

		for(int j=1; j<=N; j++)
		{
			if(j==i) continue;
			for(int k=1; k<=N; k++)
			{
				if(k==i) continue;
				if(k==j) continue;
				C[j][k]=0;
				for(int p=1; p<=M; p++)
				{
					if(ccw(A[j]-A[i], B[p]-A[i])>0 && ccw(A[k]-A[j], B[p]-A[j])>0 && ccw(A[i]-A[k], B[p]-A[k])>0) C[j][k]++;
				}
			}
		}

		for(int j=0; j<V.size(); j++)
		{
			dp[j]=40;
			for(int k=0; k<j; k++)
			{
				dp[j]=min(dp[j], dp[k]+20-C[V[k]][V[j]]*111);
			}
			ans=min(ans, dp[j]);
		}
	}
	printf("%d\n", ans+M*111);
}

Compilation message

fence.cpp: In function 'int main()':
fence.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int j=0; j<V.size(); j++)
      |                ~^~~~~~~~~
fence.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
fence.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fence.cpp:29:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  for(int i=1; i<=M; i++) scanf("%d%d", &B[i].x, &B[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 380 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 496 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct