結果

問題 No.180 美しいWhitespace (2)
ユーザー TawaraTawara
提出日時 2015-08-26 21:19:03
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,493 bytes
コンパイル時間 616 ms
コンパイル使用メモリ 73,588 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-25 18:35:35
合計ジャッジ時間 12,930 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 3 ms
4,376 KB
testcase_05 AC 8 ms
4,376 KB
testcase_06 AC 31 ms
4,376 KB
testcase_07 AC 63 ms
4,380 KB
testcase_08 AC 143 ms
4,380 KB
testcase_09 AC 305 ms
4,376 KB
testcase_10 AC 303 ms
4,376 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 951 ms
4,376 KB
testcase_17 AC 978 ms
4,376 KB
testcase_18 AC 900 ms
4,376 KB
testcase_19 AC 421 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 WA -
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 WA -
testcase_29 AC 1 ms
4,376 KB
testcase_30 AC 601 ms
4,376 KB
testcase_31 WA -
testcase_32 AC 3 ms
4,376 KB
testcase_33 WA -
testcase_34 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

typedef vector <int> VI;
typedef vector <VI> VVI;
typedef vector <string> VS;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, LL> PIL;
typedef vector <PIL> VPIL;


#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define sort(c) sort((c).begin(),(c).end())

#define range(i,a,b) for(int i=(a); i < (b); i++)
#define rep(i,n) range(i,0,n)

#define MAX_INT 2147483647
#define MAX_F 1000000000000

pair <LL,LL> func(LL x, LL tmp_x, LL f_x, int a[], int b[], int N){
	LL max_f = 0, min_f = MAX_F, f_tmpx;
	rep(i,N){
		f_tmpx = a[i]+b[i]*tmp_x;
		max_f = max(max_f, f_tmpx);
		min_f = min(min_f, f_tmpx);
	}
	f_tmpx = max_f - min_f;
	if(f_tmpx < f_x || (f_tmpx == f_x && tmp_x < x))
		return pair <LL,LL> (tmp_x,f_tmpx);
	else
		return pair <LL,LL> (x,f_x);
}
int main(){
	int N;
	pair <LL,LL> res;
	LL tmp_x;
	cin >> N;
	int a[N], b[N];
	rep(i,N){cin >> a[i] >> b[i];}
	res = func(1,1,MAX_F,a,b,N);
	rep(i,N-1)
		range(j,i+1,N){
			if(b[i]==b[j]) continue;
			tmp_x = - (a[i] - a[j])/(b[i]-b[j]);
			if (tmp_x < 1) continue;
			res = func(res.first,tmp_x,res.second,a,b,N);
			if (abs(a[i] - a[j])%abs(b[i]-b[j]) > 0){
				res = func(res.first,tmp_x+1,res.second,a,b,N);
			}
		}
	cout << res.first << endl;
	return 0;
}
0