oj.uz

Submission #659885

# Submission time Handle Problem Language Result Execution time Memory
659885 2022-11-19T15:59:03 Z mgl_diamond Rabbit Carrot (LMIO19_triusis) C++14
14 / 100
 605 ms 98616 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][5001];

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 38 ms 98124 KB Output is correct
2 Correct 38 ms 98084 KB Output is correct
3 Correct 35 ms 98184 KB Output is correct
4 Correct 37 ms 98112 KB Output is correct
5 Correct 36 ms 98172 KB Output is correct
6 Correct 36 ms 98124 KB Output is correct
7 Correct 36 ms 98116 KB Output is correct
8 Correct 36 ms 98128 KB Output is correct
9 Correct 294 ms 98192 KB Output is correct
10 Correct 39 ms 98112 KB Output is correct
11 Correct 51 ms 98132 KB Output is correct
12 Correct 36 ms 98188 KB Output is correct
13 Correct 37 ms 98088 KB Output is correct
14 Correct 37 ms 98204 KB Output is correct
15 Correct 36 ms 98128 KB Output is correct
16 Correct 36 ms 98124 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98124 KB Output is correct
2 Correct 38 ms 98084 KB Output is correct
3 Correct 35 ms 98184 KB Output is correct
4 Correct 37 ms 98112 KB Output is correct
5 Correct 36 ms 98172 KB Output is correct
6 Correct 36 ms 98124 KB Output is correct
7 Correct 36 ms 98116 KB Output is correct
8 Correct 36 ms 98128 KB Output is correct
9 Correct 294 ms 98192 KB Output is correct
10 Correct 39 ms 98112 KB Output is correct
11 Correct 51 ms 98132 KB Output is correct
12 Correct 36 ms 98188 KB Output is correct
13 Correct 37 ms 98088 KB Output is correct
14 Correct 37 ms 98204 KB Output is correct
15 Correct 36 ms 98128 KB Output is correct
16 Correct 36 ms 98124 KB Output is correct
17 Correct 40 ms 98084 KB Output is correct
18 Correct 37 ms 98168 KB Output is correct
19 Correct 37 ms 98188 KB Output is correct
20 Correct 317 ms 98532 KB Output is correct
21 Incorrect 605 ms 98616 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98084 KB Output is correct
2 Correct 37 ms 98168 KB Output is correct
3 Correct 37 ms 98188 KB Output is correct
4 Correct 317 ms 98532 KB Output is correct
5 Incorrect 605 ms 98616 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98084 KB Output is correct
2 Correct 37 ms 98168 KB Output is correct
3 Correct 37 ms 98188 KB Output is correct
4 Correct 317 ms 98532 KB Output is correct
5 Incorrect 605 ms 98616 KB Output isn't correct
6 Halted 0 ms 0 KB -