torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #155, Division 2, B : Jury Size

概要

N 個のイベントの準備をする。
各イベントについては、日付、準備に必要な人数 p 、準備にかかる期間 t が与えられる。
一人のスタッフは一日に丁度一つのイベントの準備に関わることができる。
準備はイベントの t 日前から始め、一日前に完了しなければならない。
必要なスタッフの最小人数を求めよ。

解法

月日を一次元配列として扱います。
各イベントについて、日付から配列インデックスを計算し、これを idx とします。
すると問題は、区間 [ idx - t, idx ) に p を一様に加算し、配列中の最大値を求める問題に帰着されます。
いもす法を用いると解けます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

#define ALL( c ) (c).begin(), (c).end()

const int DAYS[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
VI csumDays;

int getIndex( int m, int d )
{
	return csumDays[ 12 ] + csumDays[ m - 1 ] + d;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

#ifdef ONLINE_JUDGE
	freopen( "input.txt", "r", stdin );
	freopen( "output.txt", "w", stdout );
#endif

	int n;
	cin >> n;

	csumDays.resize( 1, 0 );
	partial_sum( DAYS, DAYS + 12, back_inserter( csumDays ) );

	VI ary( 800 );

	REP( i, 0, n )
	{
		int m, d, p, t;
		cin >> m >> d >> p >> t;

		int idx = getIndex( m, d );

		ary[ idx - t ] += p;
		ary[ idx ] -= p;
	}

	VI csum;
	partial_sum( ALL( ary ), back_inserter( csum ) );

	cout << *max_element( ALL( csum ) ) << endl;

	return 0;
}