結果

問題 No.335 門松宝くじ
コンテスト
ユーザー はまやんはまやん
提出日時 2016-07-10 15:40:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,338 bytes
コンパイル時間 1,472 ms
コンパイル使用メモリ 170,264 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 10:15:58
合計ジャッジ時間 2,935 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 WA * 5
権限があれば一括ダウンロードができます

ソースコード

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 + 2, N) {
		int _max = max(E[m][i], E[m][j]);
		int _min = min(E[m][i], E[m][j]);

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

		if (_max < _max_st)
		{
			cnt[_max_st]++;
		}
		else if (_min_st < _min)
		{
			cnt[_max]++;
		}
		else
		{
			cnt[0]++;
		}
	}

	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