Submission #65252265

Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> K;
	vector<int>num(1000001);
	for (int i = 0; i < N; i++) {
		cin >> M;
		num[M]++;
	}
	if (K == 0) {
		int ans = 0;
		for (auto i : num) {
			ans += max(i - 1, 0);
		}
		cout << ans << endl;
		return 0;
	}
	int ans = 0;
	vector<vector<int>>dp(1000001, vector<int>(2));
	for (int i = 0; i < K; i++) {
		dp[i][0] = 0;
		dp[i][1] = num[i];
	}
	for (int i = K; i <= 1000000; i++) {
		dp[i][0] = dp[i - K][1];
		dp[i][1] = min(dp[i - K][1], dp[i - K][0]) + num[i];
	}
	for (int i = 0; i < K; i++) {
		ans += min(dp[1000000 - i][0], dp[1000000 - i][1]);
	}
	cout << ans << endl;
}

Submission Info

Submission Time
Task D - Forbidden Difference
User olphe
Language C++ 23 (gcc 12.2)
Score 425
Code Size 1289 Byte
Status AC
Exec Time 72 ms
Memory 61780 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 40
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 49 ms 61676 KiB
00_sample_02.txt AC 48 ms 61688 KiB
00_sample_03.txt AC 49 ms 61652 KiB
01_random_01.txt AC 55 ms 61612 KiB
01_random_02.txt AC 50 ms 61580 KiB
01_random_03.txt AC 55 ms 61624 KiB
01_random_04.txt AC 51 ms 61728 KiB
01_random_05.txt AC 54 ms 61636 KiB
01_random_06.txt AC 53 ms 61636 KiB
01_random_07.txt AC 10 ms 7036 KiB
01_random_08.txt AC 51 ms 61776 KiB
01_random_09.txt AC 54 ms 61596 KiB
01_random_10.txt AC 54 ms 61704 KiB
01_random_11.txt AC 55 ms 61588 KiB
01_random_12.txt AC 53 ms 61716 KiB
01_random_13.txt AC 56 ms 61644 KiB
01_random_14.txt AC 52 ms 61780 KiB
01_random_15.txt AC 10 ms 6972 KiB
01_random_16.txt AC 51 ms 61556 KiB
01_random_17.txt AC 56 ms 61648 KiB
01_random_18.txt AC 54 ms 61552 KiB
01_random_19.txt AC 56 ms 61680 KiB
01_random_20.txt AC 53 ms 61600 KiB
01_random_21.txt AC 55 ms 61608 KiB
01_random_22.txt AC 55 ms 61712 KiB
01_random_23.txt AC 11 ms 7072 KiB
01_random_24.txt AC 53 ms 61716 KiB
01_random_25.txt AC 72 ms 61776 KiB
01_random_26.txt AC 52 ms 61708 KiB
01_random_27.txt AC 68 ms 61688 KiB
01_random_28.txt AC 51 ms 61620 KiB
01_random_29.txt AC 72 ms 61620 KiB
01_random_30.txt AC 70 ms 61636 KiB
01_random_31.txt AC 20 ms 7136 KiB
01_random_32.txt AC 52 ms 61692 KiB
02_handmade_01.txt AC 59 ms 61616 KiB
02_handmade_02.txt AC 12 ms 6992 KiB
02_handmade_03.txt AC 3 ms 6952 KiB
02_handmade_04.txt AC 48 ms 61620 KiB
02_handmade_05.txt AC 52 ms 61648 KiB