oj.uz

Submission #976083

# Submission time Handle Problem Language Result Execution time Memory
976083 2024-05-06T07:16:13 Z vjudge1 Watching (JOI13_watching) C++17
Compilation error
 0 ms 0 KB 
/*

*/

#include<bits/stdc++.h>
using namespace std;

#define int long long;

const int inf = 2e9;

int n, p, q, k;
vector<int> a, nxt1, nxt2;
vector<vector<int>> dp;

int f(int i, int b) {
	if (i == n) {
		return 0;
	}
	if (dp[i][b] != -1) {
		return dp[i][b];
	}
	int ret = f(nxt1[i], b) + 1;
	if (b > 0) ret = min(ret, f(nxt2[i], b - 1));
	return dp[i][b] = ret;
}

signed main() {
	cin >> n >> p >> q;

	a.resize(n);
	nxt1.resize(n);
	nxt2.resize(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int lo = 1, hi = 1e9, ans = 1e9;
	while (lo <= hi) {
		int k = (lo + hi) >> 1;

		for (int i = 0; i < n; i++) {
			bool ok = 0;
			for (int j = i + 1; j < n; j++) {
				if (a[j] > a[i] + k) {
					nxt1[i] = j, ok = 1;
					break;
				} 
			}
			if (!ok) {
				nxt1[i] = n;
			}
			ok = 0;
			for (int j = i + 1; j < n; j++) {
				if (a[j] > a[i] + 2 * k) {
					nxt2[i] = j, ok = 1;
					break;
				} 
			}
			if (!ok) {
				nxt2[i] = n;
			}
		}

		dp.assign(n, vector<int>(q + 1, -1));

		if (f(0, q) <= p) {
			hi = k - 1, ans = k;
		} else {
			lo = k + 1;
		}
	}

	cout << ans << '\n';
}

Compilation message

watching.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
watching.cpp:10:7: note: in expansion of macro 'int'
   10 | const int inf = 2e9;
      |       ^~~
watching.cpp:10:11: error: 'inf' does not name a type; did you mean 'ynf'?
   10 | const int inf = 2e9;
      |           ^~~
      |           ynf
watching.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
watching.cpp:12:1: note: in expansion of macro 'int'
   12 | int n, p, q, k;
      | ^~~
watching.cpp:12:5: error: 'n' does not name a type; did you mean 'yn'?
   12 | int n, p, q, k;
      |     ^
      |     yn
watching.cpp:8:18: error: template argument 1 is invalid
    8 | #define int long long;
      |                  ^~~~
watching.cpp:13:8: note: in expansion of macro 'int'
   13 | vector<int> a, nxt1, nxt2;
      |        ^~~
watching.cpp:8:18: error: template argument 2 is invalid
    8 | #define int long long;
      |                  ^~~~
watching.cpp:13:8: note: in expansion of macro 'int'
   13 | vector<int> a, nxt1, nxt2;
      |        ^~~
watching.cpp:13:11: error: expected unqualified-id before '>' token
   13 | vector<int> a, nxt1, nxt2;
      |           ^
watching.cpp:8:18: error: template argument 1 is invalid
    8 | #define int long long;
      |                  ^~~~
watching.cpp:14:15: note: in expansion of macro 'int'
   14 | vector<vector<int>> dp;
      |               ^~~
watching.cpp:8:18: error: template argument 2 is invalid
    8 | #define int long long;
      |                  ^~~~
watching.cpp:14:15: note: in expansion of macro 'int'
   14 | vector<vector<int>> dp;
      |               ^~~
watching.cpp:14:8: error: template argument 1 is invalid
   14 | vector<vector<int>> dp;
      |        ^
watching.cpp:14:8: error: template argument 2 is invalid
watching.cpp:14:18: error: expected unqualified-id before '>>' token
   14 | vector<vector<int>> dp;
      |                  ^~
watching.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
watching.cpp:16:1: note: in expansion of macro 'int'
   16 | int f(int i, int b) {
      | ^~~
watching.cpp:8:22: error: expected ')' before ';' token
    8 | #define int long long;
      |                      ^
watching.cpp:16:7: note: in expansion of macro 'int'
   16 | int f(int i, int b) {
      |       ^~~
watching.cpp:16:6: note: to match this '('
   16 | int f(int i, int b) {
      |      ^
watching.cpp:8:22: error: expected constructor, destructor, or type conversion before ';' token
    8 | #define int long long;
      |                      ^
watching.cpp:16:7: note: in expansion of macro 'int'
   16 | int f(int i, int b) {
      |       ^~~
watching.cpp:16:11: error: 'i' does not name a type
   16 | int f(int i, int b) {
      |           ^
watching.cpp:16:18: error: 'b' does not name a type
   16 | int f(int i, int b) {
      |                  ^
watching.cpp: In function 'int main()':
watching.cpp:29:9: error: 'n' was not declared in this scope; did you mean 'yn'?
   29 |  cin >> n >> p >> q;
      |         ^
      |         yn
watching.cpp:29:14: error: 'p' was not declared in this scope
   29 |  cin >> n >> p >> q;
      |              ^
watching.cpp:29:19: error: 'q' was not declared in this scope
   29 |  cin >> n >> p >> q;
      |                   ^
watching.cpp:31:2: error: 'a' was not declared in this scope
   31 |  a.resize(n);
      |  ^
watching.cpp:32:2: error: 'nxt1' was not declared in this scope
   32 |  nxt1.resize(n);
      |  ^~~~
watching.cpp:33:2: error: 'nxt2' was not declared in this scope
   33 |  nxt2.resize(n);
      |  ^~~~
watching.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
watching.cpp:35:7: note: in expansion of macro 'int'
   35 |  for (int i = 0; i < n; i++) {
      |       ^~~
watching.cpp:35:11: error: 'i' was not declared in this scope
   35 |  for (int i = 0; i < n; i++) {
      |           ^
watching.cpp:35:23: error: expected ')' before ';' token
   35 |  for (int i = 0; i < n; i++) {
      |      ~                ^
      |                       )
watching.cpp:35:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   35 |  for (int i = 0; i < n; i++) {
      |  ^~~
watching.cpp:35:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   35 |  for (int i = 0; i < n; i++) {
      |                         ^
watching.cpp:35:25: error: 'i' was not declared in this scope
watching.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
watching.cpp:39:2: note: in expansion of macro 'int'
   39 |  int lo = 1, hi = 1e9, ans = 1e9;
      |  ^~~
watching.cpp:39:6: error: 'lo' was not declared in this scope; did you mean 'log'?
   39 |  int lo = 1, hi = 1e9, ans = 1e9;
      |      ^~
      |      log
watching.cpp:39:14: error: 'hi' was not declared in this scope
   39 |  int lo = 1, hi = 1e9, ans = 1e9;
      |              ^~
watching.cpp:39:24: error: 'ans' was not declared in this scope; did you mean 'abs'?
   39 |  int lo = 1, hi = 1e9, ans = 1e9;
      |                        ^~~
      |                        abs
watching.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
watching.cpp:41:3: note: in expansion of macro 'int'
   41 |   int k = (lo + hi) >> 1;
      |   ^~~
watching.cpp:41:7: error: 'k' was not declared in this scope
   41 |   int k = (lo + hi) >> 1;
      |       ^
watching.cpp:8:18: error: declaration does not declare anything [-fpermissive]
    8 | #define int long long;
      |                  ^~~~
watching.cpp:43:8: note: in expansion of macro 'int'
   43 |   for (int i = 0; i < n; i++) {
      |        ^~~
watching.cpp:43:24: error: expected ')' before ';' token
   43 |   for (int i = 0; i < n; i++) {
      |       ~                ^
      |                        )
watching.cpp:43:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |   for (int i = 0; i < n; i++) {
      |   ^~~
watching.cpp:43:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |   for (int i = 0; i < n; i++) {
      |                          ^
watching.cpp:66:3: error: 'dp' was not declared in this scope
   66 |   dp.assign(n, vector<int>(q + 1, -1));
      |   ^~
watching.cpp:8:18: error: template argument 1 is invalid
    8 | #define int long long;
      |                  ^~~~
watching.cpp:66:23: note: in expansion of macro 'int'
   66 |   dp.assign(n, vector<int>(q + 1, -1));
      |                       ^~~
watching.cpp:8:18: error: template argument 2 is invalid
    8 | #define int long long;
      |                  ^~~~
watching.cpp:66:23: note: in expansion of macro 'int'
   66 |   dp.assign(n, vector<int>(q + 1, -1));
      |                       ^~~
watching.cpp:66:26: error: expected primary-expression before '>' token
   66 |   dp.assign(n, vector<int>(q + 1, -1));
      |                          ^
watching.cpp:68:7: error: 'f' was not declared in this scope
   68 |   if (f(0, q) <= p) {
      |       ^