結果

問題 No.335 門松宝くじ
ユーザー はまやんはまやんはまやんはまやん
提出日時 2016-07-10 15:58:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 177 ms / 2,000 ms
コード長 2,918 bytes
コンパイル時間 1,730 ms
コンパイル使用メモリ 172,720 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 10:20:46
合計ジャッジ時間 3,625 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 44 ms
5,248 KB
testcase_06 AC 67 ms
5,248 KB
testcase_07 AC 116 ms
5,248 KB
testcase_08 AC 118 ms
5,248 KB
testcase_09 AC 176 ms
5,248 KB
testcase_10 AC 175 ms
5,248 KB
testcase_11 AC 176 ms
5,248 KB
testcase_12 AC 177 ms
5,248 KB
testcase_13 AC 174 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)



typedef long long ll;
template<class V, int NV> class SegTreeMax {
public:
	static V const def = -(1LL << 60);
	V comp(V l, V r) { return max(l, r); };

	vector<V> val;
	SegTreeMax() { val = vector<V>(NV * 2, def); }

	V getval(int l, int r) { //[l,r]
		l += NV; r += NV + 1;
		V ret = def;
		while (l < r) {
			if (l & 1) ret = comp(ret, val[l++]);
			if (r & 1) ret = comp(ret, val[--r]);
			l /= 2; r /= 2;
		}
		return ret;
	}
	void update(int i, V v) {
		i += NV;
		val[i] = v;
		while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
	}
};
template<class V, int NV> class SegTreeMin {
public:
	static V const def = (1LL << 31) - 1;
	V comp(V l, V r) { return min(l, r); };

	vector<V> val;
	SegTreeMin() { val = vector<V>(NV * 2, def); }

	V getval(int l, int r) { //[l,r]
		l += NV; r += NV + 1;
		V ret = def;
		while (l < r) {
			if (l & 1) ret = comp(ret, val[l++]);
			if (r & 1) ret = comp(ret, val[--r]);
			l /= 2; r /= 2;
		}
		return ret;
	}
	void update(int i, V v) {
		i += NV;
		val[i] = v;
		while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
	}
};
//-----------------------------------------------------------------
int N, M;
int E[3][800];
//-----------------------------------------------------------------
double calc(int m) {
	SegTreeMax<ll, 1 << 10> st_max;
	SegTreeMin<ll, 1 << 10> st_min;

	rep(i, 0, N) st_max.update(i, E[m][i]);
	rep(i, 0, N) st_min.update(i, E[m][i]);

	int cnt[805];
	rep(i, 0, N + 1) cnt[i] = 0;
	rep(i, 0, N) rep(j, i + 1, N) {
		int _max = max(E[m][i], E[m][j]);
		int _min = min(E[m][i], E[m][j]);

		int idx = 0;

		if (j != N - 1) {
			if (E[m][i] < E[m][j]) {
				int _min_st = st_min.getval(j + 1, N - 1);
				if (_min_st < E[m][j]) idx = max(idx, E[m][j]);
			}
			else {
				int _max_st = st_max.getval(j + 1, N - 1);
				if (E[m][j] < _max_st) idx = max(idx, max(E[m][i], _max_st));
			}
		}

		if (i != 0) {
			if (E[m][i] < E[m][j]) {
				int _max_st = st_max.getval(0, i - 1);
				if (E[m][i] < _max_st) idx = max(idx, max(E[m][j], _max_st));
			}
			else {
				int _min_st = st_min.getval(0, i - 1);
				if (_min_st < E[m][i]) idx = max(idx, E[m][i]);
			}
		}

		if (j - i != 1) {
			int _max_st = st_max.getval(i + 1, j - 1);
			int _min_st = st_max.getval(i + 1, j - 1);

			if (_max < _max_st) idx = max(idx, _max_st);
			if (_min_st < _min) idx = max(idx, _max);
		}

		cnt[idx]++;
	}

	int sum = 0;
	rep(i, 0, N + 1) sum += cnt[i];

	double ret = 0;
	rep(i, 0, N + 1) ret += (double)i * ((double)cnt[i] / (double)sum);
	return ret;
}
//-----------------------------------------------------------------
int main()
{
	scanf("%d %d", &N, &M);
	rep(i, 0, M) rep(j, 0, N) scanf("%d", &E[i][j]);

	int ans = 0;
	double ans_p = -1;
	rep(i, 0, M) {
		float p = calc(i);
		if (ans_p < p) {
			ans = i;
			ans_p = p;
		}
	}

	printf("%d\n", ans);
}
0