結果

問題 No.335 門松宝くじ
コンテスト
ユーザー Ysmr_Ry
提出日時 2016-03-02 10:35:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 608 ms / 2,000 ms
コード長 2,677 bytes
コンパイル時間 644 ms
コンパイル使用メモリ 55,308 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-24 13:27:05
合計ジャッジ時間 5,375 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:82:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |         scanf( "%d%d", &N, &M );
      |         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:92:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   92 |                         scanf( "%d", E+j );
      |                         ~~~~~^~~~~~~~~~~~~

ソースコード

diff # 

// yukicoder 335 (http://yukicoder.me/problems/936)
#include<cstdio>
#include<algorithm>
#include<vector>
#include<limits>
#define rep(i,a) for(int i=0;i<(a);++i)

typedef long long ll;
typedef std::pair<ll, int> P;

const int MAX_M = 3, MAX_N = 800, INF = std::numeric_limits<int>::max()>>1;

struct SegTree
{
	std::vector<int> datMi, datMa;
	size_t sz;

	SegTree( size_t n )
	{
		sz = 1;
		while( sz < n )
			sz <<= 1;

		datMi.resize( 2*sz-1 );
		datMa.resize( 2*sz-1 );

		rep( i, 2*sz-1 )
		{
			datMi[i] = INF;
			datMa[i] = -INF;
		}
	}

	void update( int k, int x )
	{
		k += sz-1;
		datMi[k] = datMa[k] = x;

		while( k > 0 )
		{
			k = (k-1)/2;

			datMi[k] = std::min( datMi[2*k+1], datMi[2*k+2] );
			datMa[k] = std::max( datMa[2*k+1], datMa[2*k+2] );
		}

		return;
	}

	int query( int a, int b, int k, int l, int r, bool isma )
	{
		if( b <= l || r <= a )
			return isma?-INF:INF;
		else if( a <= l && r <= b )
			return (isma?datMa:datMi)[k];
		else
		{
			int vl = query( a, b, 2*k+1, l, l+r>>1, isma ),
				vr = query( a, b, 2*k+2, l+r>>1, r, isma );

			return isma?std::max(vl,vr):std::min(vl,vr);
		}
	}
};

int N, M;
int E[MAX_N];

bool judge( int a, int b, int c )
{
	if( a == b || b == c || c == a )
		return false;

	int arr[3] = { a, b, c };
	std::sort( arr, arr+3 );

	return arr[1] == a || arr[1] == c;
}

int main()
{
	scanf( "%d%d", &N, &M );

	P ans( -1, 0 );

	rep( i, M )
	{
		SegTree seg( N );

		rep( j, N )
		{
			scanf( "%d", E+j );
			seg.update( j, E[j] );
		}

		ll s = 0;
		rep( j, N ) rep( k, j )
		{
			int res = 0;

			if( k > 0 )
			{
				int ma = seg.query( 0, k, 0, 0, seg.sz, true ),
					mi = seg.query( 0, k, 0, 0, seg.sz, false );

				if( judge( ma, E[k], E[j] ) )
					res = std::max( res, std::max( ma, std::max( E[k], E[j] ) ) );
				if( judge( mi, E[k], E[j] ) )
					res = std::max( res, std::max( mi, std::max( E[k], E[j] ) ) );
			}
			
			if( k+1 < j )
			{
				int ma = seg.query( k+1, j, 0, 0, seg.sz, true ),
					mi = seg.query( k+1, j, 0, 0, seg.sz, false );

				if( judge( E[k], ma, E[j] ) )
					res = std::max( res, std::max( ma, std::max( E[k], E[j] ) ) );
				if( judge( E[k], mi, E[j] ) )
					res = std::max( res, std::max( mi, std::max( E[k], E[j] ) ) );
			}

			if( j+1 < N )
			{
				int ma = seg.query( j+1, N, 0, 0, seg.sz, true ),
					mi = seg.query( j+1, N, 0, 0, seg.sz, false );

				if( judge( E[k], E[j], ma ) )
					res = std::max( res, std::max( ma, std::max( E[k], E[j] ) ) );
				if( judge( E[k], E[j], mi ) )
					res = std::max( res, std::max( mi, std::max( E[k], E[j] ) ) );
			}

			s += res;
		}

		ans = std::max( ans, P( s, -i ) );
	}

	printf( "%d\n", -ans.second );

	return 0;
}
0