Submission #659885

#	Time	Username	Problem	Language	Result	Execution time	Memory
659885		mgl_diamond	Rabbit Carrot (LMIO19_triusis)	C++14	14 / 100	605 ms	98616 KiB

triusis

#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 (stderr)

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 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37