oj.uz

Submission #61397

# Submission time Handle Problem Language Result Execution time Memory
61397 2018-07-25T17:39:25 Z kingpig9 Mountains (IOI17_mountains) C++11
0 / 100
 4 ms 492 KB 
#include <bits/stdc++.h>
#include "mountains.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2018;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
int dp[MAXN][MAXN], A[MAXN];

int maximum_deevs (vector<int> v) {
	N = v.size();
	copy(all(v), A);

	for (int rt = 0; rt < N; rt++) {
		dp[rt][rt] = 1;

		int block = rt;	//which one IS BLOCKING others?
		int notsee = 0;	//which one you guarantee not see?

		for (int lt = rt - 1; lt >= 0; lt--) {
			dp[lt][rt] = dp[lt][rt - 1];
			if (ll(rt - block) * (A[lt] - A[block]) >= ll(lt - block) * (A[rt] - A[block])) {
				if (lt + 1 <= block - 1) {
					notsee += dp[lt + 1][block - 1];
				}
				block = lt;
			}

			if (lt < block) {
				dp[lt][rt] = max(dp[lt][rt], notsee + 1 + dp[lt][block - 1]);
			}
		}
	}
	return dp[0][N - 1];
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 472 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Incorrect 3 ms 492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 472 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Incorrect 3 ms 492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 472 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Incorrect 3 ms 492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 472 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Incorrect 3 ms 492 KB Output isn't correct
8 Halted 0 ms 0 KB -