IOI 2004

Submission #455887

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()
{
	freopen("hermes.in","r",stdin);
	freopen("hermes.out","w",stdout);
	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状態 WA
Score得点 0
Source lengthソースコード長 1732 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:48:32: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:49:34: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:50:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:51: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 0 / 5 01
Set02 0 / 5 02
Set03 0 / 5 03
Set04 0 / 5 04
Set05 0 / 5 05
Set06 0 / 5 06
Set07 0 / 5 07
Set08 0 / 5 08
Set09 0 / 5 09
Set10 0 / 5 10
Set11 0 / 5 11
Set12 0 / 5 12
Set13 0 / 5 13
Set14 0 / 5 14
Set15 0 / 5 15
Set16 0 / 5 16
Set17 0 / 5 17
Set18 0 / 5 18
Set19 0 / 5 19
Set20 0 / 5 20

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01 WA
02 WA
03 WA
04 WA
05 WA
06 WA
07 WA
08 WA
09 WA
10 WA
11 WA
12 WA
13 WA
14 WA
15 WA
16 WA
17 WA
18 WA
19 WA
20 WA