Submission #257205

#	Time	Username	Problem	Language	Result	Execution time	Memory
257205		Lawliet	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	131 ms	11256 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 100010;
const int MAXM = 1000010;

int n, m, d;

int sQtd[MAXN];

vector<int> day[MAXN];

bool test(lli k)
{
	lli mn = 0;

	for(int i = 1 ; i <= n ; i++)
	{
		lli curValue = sQtd[i] - k*i - k*d;
		if( curValue > mn ) return false;

		mn = min( mn , sQtd[i] - k*i );
	}

	return true;
}

int bs()
{
	int l = 1;
	int r = m;

	while( l < r )
	{
		int m = ( l + r )/2;

		if( test( m ) ) r = m;
		else l = m + 1;
	}

	return r;
}

int main()
{
	scanf("%d %d %d",&n,&d,&m);

	for(int i = 1 ; i <= m ; i++)
	{
		int d;
		scanf("%d",&d);

		day[d].push_back( i );
	}

	for(int i = 1 ; i <= n ; i++)
		sQtd[i] = sQtd[i - 1] + (int)day[i].size();

	int ans = bs();

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

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
jobs.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&d);
   ~~~~~^~~~~~~~~

• Subtask 1: 0 / 100