Submission #181494


Source Code Expand

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector<int>x,y;
int a[85],b[85];
int dp[85][85][85];

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d",&a[i],&b[i]);
		x.push_back(a[i]);
		y.push_back(b[i]);
	}
	x.push_back(0); y.push_back(0);
	sort(x.begin(),x.end());
	sort(y.begin(),y.end());
	x.erase(unique(x.begin(),x.end()),x.end());
	y.erase(unique(y.begin(),y.end()),y.end());
	for(int i=0;i<n;i++)
	{
		a[i] = lower_bound(x.begin(),x.end(),a[i])-x.begin();
		b[i] = lower_bound(y.begin(),y.end(),b[i])-y.begin();
	}
	for(int i=0;i<85;i++) for(int j=0;j<85;j++) for(int k=0;k<85;k++) dp[i][j][k] = 1e9;
	int bx = lower_bound(x.begin(),x.end(),0)-x.begin();
	int by = lower_bound(y.begin(),y.end(),0)-y.begin();
	dp[0][bx][by] = 0;
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<x.size();j++)
		{
			for(int k=0;k<y.size();k++)
			{
				if(dp[i][j][k] == 1e9) continue;
				dp[i+1][a[i]][k] = min(dp[i+1][a[i]][k],dp[i][j][k] + abs(x[a[i]]-x[j]));
				dp[i+1][j][b[i]] = min(dp[i+1][j][b[i]],dp[i][j][k] + abs(y[b[i]]-y[k]));
			}
		}
	}
	int res = 1e9;
	for(int j=0;j<x.size();j++) for(int k=0;k<y.size();k++) res = min(res,dp[n][j][k]);
	printf("%d\n",res);
}

Submission Info

Submission Time
Task 1 - Hermes
User IH19980412
Language C++ (G++ 4.6.4)
Score 50
Code Size 1276 Byte
Status RE
Exec Time 274 ms
Memory 3232 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:14:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:17:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name Set01 Set02 Set03 Set04 Set05 Set06 Set07 Set08 Set09 Set10 Set11 Set12 Set13 Set14 Set15 Set16 Set17 Set18 Set19 Set20
Score / Max Score 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5 0 / 5
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
RE × 1
Set Name Test Cases
Set01 01
Set02 02
Set03 03
Set04 04
Set05 05
Set06 06
Set07 07
Set08 08
Set09 09
Set10 10
Set11 11
Set12 12
Set13 13
Set14 14
Set15 15
Set16 16
Set17 17
Set18 18
Set19 19
Set20 20
Case Name Status Exec Time Memory
01 AC 25 ms 3104 KB
02 AC 26 ms 3100 KB
03 AC 26 ms 3104 KB
04 AC 25 ms 3100 KB
05 AC 26 ms 3100 KB
06 AC 25 ms 3108 KB
07 AC 24 ms 3232 KB
08 AC 25 ms 3112 KB
09 AC 26 ms 3172 KB
10 AC 25 ms 3232 KB
11 RE 262 ms 808 KB
12 RE 259 ms 800 KB
13 RE 259 ms 920 KB
14 RE 264 ms 676 KB
15 RE 259 ms 676 KB
16 RE 260 ms 676 KB
17 RE 270 ms 680 KB
18 RE 274 ms 676 KB
19 RE 258 ms 924 KB
20 RE 254 ms 924 KB