IOI 2004

Submission #455893

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;
			MIN(dp[y][0],tmp[j][0]+abs(X[i]-x));
			MIN(dp[x][1],tmp[j][0]+abs(Y[i]-y));
			
			x=j,y=Y[i-1];
			MIN(dp[y][0],tmp[j][1]+abs(x-X[i]));
			MIN(dp[x][1],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状態 AC
Score得点 100
Source lengthソースコード長 1654 Byte
File nameファイル名
Exec time実行時間 435 ms
Memory usageメモリ使用量 1112 KB

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 5 / 5 19
Set20 5 / 5 20

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01 AC 37 ms 888 KB
02 AC 34 ms 892 KB
03 AC 36 ms 952 KB
04 AC 36 ms 952 KB
05 AC 34 ms 892 KB
06 AC 39 ms 980 KB
07 AC 32 ms 892 KB
08 AC 32 ms 892 KB
09 AC 33 ms 988 KB
10 AC 34 ms 984 KB
11 AC 35 ms 956 KB
12 AC 36 ms 960 KB
13 AC 37 ms 888 KB
14 AC 38 ms 1048 KB
15 AC 41 ms 896 KB
16 AC 54 ms 892 KB
17 AC 234 ms 984 KB
18 AC 376 ms 1024 KB
19 AC 435 ms 1112 KB
20 AC 135 ms 1024 KB