oj.uz

Submission #51471

# Submission time Handle Problem Language Result Execution time Memory
51471 2018-06-18T03:37:12 Z MoesashiMinamoto Watching (JOI13_watching) C++14
100 / 100
 137 ms 16380 KB 
#include <bits/stdc++.h>

using namespace std;

int n, p, q;

int a[2003];
int dp[2003][2003];
int js[2003], jb[2003];

void jump(int w)
{
	for (int i = 0; i < n; i++)
	{
		js[i] = upper_bound(a, a+n, a[i]+w-1) - a;
		jb[i] = upper_bound(a, a+n, a[i]+2*w-1) - a;
	}
}

bool chec(int w)
{
	jump(w);
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 0; i <= q; i++)
	{
		for (int j = 0; j <= p; j++)
		{
			if (dp[i][j] != -1)
			{
				if (dp[i][j] == n) return true;
				dp[i][j+1] = max(dp[i][j+1], js[dp[i][j]]);
				dp[i+1][j] = max(dp[i+1][j], jb[dp[i][j]]);
			}
		}
	}
	return false;
}

signed main()
{
	scanf("%d%d%d", &n, &p, &q);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	sort(a, a+n);
	if (p + q >= n) 
	{
		printf("1");
		return 0;
	}
	long long it = 0;
	for (int i = 33; i >= 0; i--)
	{
		if (it + (1ll << i) <= 1000000000)
		{
			long long cur = it + (1ll << i);
			if (!chec(cur))
			{
				it = cur;
			}
		}
	}
	printf("%lld", it+1);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &p, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 16120 KB Output is correct
2 Correct 2 ms 16120 KB Output is correct
3 Correct 43 ms 16176 KB Output is correct
4 Correct 3 ms 16176 KB Output is correct
5 Correct 2 ms 16176 KB Output is correct
6 Correct 2 ms 16176 KB Output is correct
7 Correct 46 ms 16200 KB Output is correct
8 Correct 46 ms 16200 KB Output is correct
9 Correct 51 ms 16332 KB Output is correct
10 Correct 47 ms 16332 KB Output is correct
11 Correct 52 ms 16332 KB Output is correct
12 Correct 49 ms 16332 KB Output is correct
13 Correct 42 ms 16332 KB Output is correct
14 Correct 40 ms 16332 KB Output is correct
15 Correct 45 ms 16332 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16340 KB Output is correct
2 Correct 2 ms 16340 KB Output is correct
3 Correct 2 ms 16340 KB Output is correct
4 Correct 3 ms 16340 KB Output is correct
5 Correct 2 ms 16340 KB Output is correct
6 Correct 3 ms 16340 KB Output is correct
7 Correct 51 ms 16380 KB Output is correct
8 Correct 72 ms 16380 KB Output is correct
9 Correct 60 ms 16380 KB Output is correct
10 Correct 54 ms 16380 KB Output is correct
11 Correct 65 ms 16380 KB Output is correct
12 Correct 137 ms 16380 KB Output is correct
13 Correct 56 ms 16380 KB Output is correct
14 Correct 54 ms 16380 KB Output is correct
15 Correct 52 ms 16380 KB Output is correct