제출 #659922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659922		mgl_diamond	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	68 ms	11152 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}, INF = 1e9+9, mxN = 2e5+5;

int n, m, a[mxN], dp[mxN];

map<int, int> mp;
void ins(int v1, int v2) {
	auto it = mp.lower_bound(v1);
	if (it!=mp.end() && it->y <= v2) return;
	it = mp.insert(it, C(v1, v2)); it->y = v2;
	while (it!=mp.begin() && prev(it)->y >= v2) mp.erase(prev(it));
}

int query(int x) {
	auto it = mp.lower_bound(x);
	if (it == mp.end()) return INF;
	return it->y;
}

void work() {
	cin >> n >> m;
	for(int i=1; i<=n; ++i) {
		cin >> a[i];
	}
	
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;

	int delta_m = 0, delta_j = 0;
	for(int i=1; i<=n+1; ++i) {
		delta_m += m; delta_j += 1;
		ins(a[i-1] - delta_m, dp[i-1] - delta_j);
		ckmin(dp[i], query(a[i] - delta_m - m) + delta_j);
	}

	cout << dp[n+1];
}

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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37