oj.uz

Submission #659887

# Submission time Handle Problem Language Result Execution time Memory
659887 2022-11-19T16:00:16 Z mgl_diamond Rabbit Carrot (LMIO19_triusis) C++14
14 / 100
 1000 ms 196392 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using db =  double;

#define conqueror_of_uraqt int main()
#define xuong cout << "\n"
#define debug(x) cout << #x << ": " << x << endl
#define rep(i,be,en) for(int i = (be); i<=(en); ++i)
#define fod(i,be,en) for(int i = (be); i>=(en); --i)
#define each(x, a)   for(auto &x: a)
#define x first
#define y second
#define vec vector
#define endl "\n"
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define uni(a) ((a).erase(unique(all(a)),(a).end()))
#define C make_pair
#define file "input"

const int mod = 1e9+7;
template<class T> bool ckmax(T &a, T b) {if (a<b) return a=b,1; return 0;}
template<class T> bool ckmin(T &a, T b) {if (a>b) return a=b,1; return 0;}
int add(int a, int b) { a+=b; if (a>=mod) a-=mod; return a; }
int neg(int a, int b) { a-=b; if (a<0) a+=mod; return a; }
int mul(int a, int b) { return (1LL*a*b) % mod; }

const db eps = 0.0000000001;
const int M[2] = {(int)1e9+9277, (int)1e9+5277}, mxN = 2e5+5;

int n, a[mxN], m;
int memo[5001][10001];

int go(int i, int h) {
	int &ret = memo[i][h];
	if (ret != -1) return ret;
	if (i == n+1) return ret = 0;
	ret = n+1;
	if (a[i+1] < h || a[i+1]-h <= m) ckmin(ret, go(i+1, a[i+1]));
	for(int nh=h; nh<=h+m; ++nh) ckmin(ret, go(i+1, nh) + 1);
	return ret;
}

void trau() {
	memset(memo, -1, sizeof(memo));
	cout << go(0, 0);
}

void work() {
	cin >> n >> m;
	for(int i=1; i<=n; ++i) {
		cin >> a[i];
	}

	trau();
	// if (n <= 5000) trau();
	// else ac();
}

conqueror_of_uraqt {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	if (fopen(file".inp", "r")) {
		freopen(file".inp", "r", stdin);
		freopen(file".out", "w", stdout);
	}
	work();
	return 0;
}

Compilation message

triusis.cpp: In function 'int main()':
triusis.cpp:68:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   freopen(file".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:69:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   freopen(file".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196072 KB Output is correct
2 Correct 76 ms 195980 KB Output is correct
3 Correct 72 ms 195940 KB Output is correct
4 Correct 71 ms 196048 KB Output is correct
5 Correct 71 ms 196044 KB Output is correct
6 Correct 85 ms 196056 KB Output is correct
7 Correct 73 ms 195952 KB Output is correct
8 Correct 80 ms 196008 KB Output is correct
9 Correct 548 ms 196140 KB Output is correct
10 Correct 79 ms 196044 KB Output is correct
11 Correct 83 ms 196024 KB Output is correct
12 Correct 71 ms 196040 KB Output is correct
13 Correct 71 ms 196052 KB Output is correct
14 Correct 72 ms 196040 KB Output is correct
15 Correct 70 ms 196052 KB Output is correct
16 Correct 71 ms 196068 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196072 KB Output is correct
2 Correct 76 ms 195980 KB Output is correct
3 Correct 72 ms 195940 KB Output is correct
4 Correct 71 ms 196048 KB Output is correct
5 Correct 71 ms 196044 KB Output is correct
6 Correct 85 ms 196056 KB Output is correct
7 Correct 73 ms 195952 KB Output is correct
8 Correct 80 ms 196008 KB Output is correct
9 Correct 548 ms 196140 KB Output is correct
10 Correct 79 ms 196044 KB Output is correct
11 Correct 83 ms 196024 KB Output is correct
12 Correct 71 ms 196040 KB Output is correct
13 Correct 71 ms 196052 KB Output is correct
14 Correct 72 ms 196040 KB Output is correct
15 Correct 70 ms 196052 KB Output is correct
16 Correct 71 ms 196068 KB Output is correct
17 Correct 73 ms 196012 KB Output is correct
18 Correct 74 ms 195996 KB Output is correct
19 Correct 71 ms 196032 KB Output is correct
20 Correct 494 ms 196384 KB Output is correct
21 Execution timed out 1105 ms 196392 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 196012 KB Output is correct
2 Correct 74 ms 195996 KB Output is correct
3 Correct 71 ms 196032 KB Output is correct
4 Correct 494 ms 196384 KB Output is correct
5 Execution timed out 1105 ms 196392 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 196012 KB Output is correct
2 Correct 74 ms 195996 KB Output is correct
3 Correct 71 ms 196032 KB Output is correct
4 Correct 494 ms 196384 KB Output is correct
5 Execution timed out 1105 ms 196392 KB Time limit exceeded
6 Halted 0 ms 0 KB -