IOI 2004

Submission #455888

Source codeソースコード

#include <cstdio>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <bitset>
#include <math.h>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<int,pii> pip;
typedef pair<ll,ll> pll;
typedef pair<ll,pii> plp;
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,a,n) for(int i=a;i<n;i++)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MAX(x,a) x=max(x,a)
#define MIN(x,a) x=min(x,a)

int N;
int X[20000],Y[20000];
int dp[2001][2];
int tmp[2001][2];

void dpset(int id,int x,int y,int s)
{
	if(x==X[id])MIN(dp[y][0],s);
	if(y==Y[id])MIN(dp[x][1],s);
}

int main()
{
	scanf("%d",&N);
	rep(i,N)scanf("%d%d",&X[i],&Y[i]),X[i]+=1000,Y[i]+=1000;
	rep(i,2001)dp[i][0]=dp[i][1]=tmp[i][0]=tmp[i][1]=1145141919;
	rep(i,2001)
	{
		dp[i][0]=abs(X[0]-1000)+abs(i-1000);
		dp[i][1]=abs(i-1000)+abs(Y[0]-1000);
	}
	repn(i,1,N)
	{
		rep(j,2001)tmp[j][0]=dp[j][0],tmp[j][1]=dp[j][1];
		rep(j,2001)dp[j][0]=dp[j][1]=1145141919;
		rep(j,2001)
		{
			int x=X[i-1],y=j;
			dpset(i,X[i],y,tmp[j][0]+abs(X[i]-x));
			dpset(i,x,Y[i],tmp[j][0]+abs(Y[i]-y));
			
			x=j,y=Y[i-1];
			dpset(i,X[i],y,tmp[j][1]+abs(x-X[i]));
			dpset(i,x,Y[i],tmp[j][1]+abs(y-Y[i]));
		}
	}
	int res=1145141919;
	rep(i,2001)rep(j,2)MIN(res,dp[i][j]);
	printf("%d\n",res);
}

Submission

Task問題 1 - Hermes
User nameユーザ名 namonakiaccount
Created time投稿日時
Language言語 C++ (G++ 4.6.4)
Status状態 TLE
Score得点 95
Source lengthソースコード長 1662 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

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

Test case

Set

Set name Score得点 / Max score Cases
Set01 5 / 5 01
Set02 5 / 5 02
Set03 5 / 5 03
Set04 5 / 5 04
Set05 5 / 5 05
Set06 5 / 5 06
Set07 5 / 5 07
Set08 5 / 5 08
Set09 5 / 5 09
Set10 5 / 5 10
Set11 5 / 5 11
Set12 5 / 5 12
Set13 5 / 5 13
Set14 5 / 5 14
Set15 5 / 5 15
Set16 5 / 5 16
Set17 5 / 5 17
Set18 5 / 5 18
Set19 0 / 5 19
Set20 5 / 5 20

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01 AC 39 ms 1024 KB
02 AC 36 ms 1088 KB
03 AC 35 ms 1016 KB
04 AC 35 ms 1024 KB
05 AC 35 ms 1020 KB
06 AC 38 ms 1040 KB
07 AC 37 ms 1080 KB
08 AC 36 ms 1020 KB
09 AC 35 ms 1020 KB
10 AC 36 ms 1080 KB
11 AC 40 ms 1020 KB
12 AC 40 ms 1088 KB
13 AC 44 ms 1080 KB
14 AC 44 ms 1020 KB
15 AC 49 ms 1020 KB
16 AC 88 ms 1020 KB
17 AC 580 ms 1148 KB
18 AC 873 ms 1148 KB
19 TLE
20 AC 310 ms 1072 KB