想DAG DP乱搞，然后MLE了6个点

// Problem: P1107 [BJWC2008] 雷涛的小猫
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1107
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define pack(x, y) (((x) << 15) | (y))
#define getx(x) ((x) >> 15)
#define gety(x) ((x) & 32767)

vector<int> graph[2005][2005];
int val[2005][2005];
int f[2005][2005];

int dfs(int r, int c) {
	if (!c) {
		return 0;
	} else if (f[r][c] != -1) {
		return f[r][c];
	}
	for (int xzcyyds : graph[r][c]) {
		int nr = getx(xzcyyds), nc = gety(xzcyyds);
		f[r][c] = max(f[r][c], dfs(nr, nc) + val[r][c]);
	}
	return f[r][c];
}


int main() {
	int n, m, delta;
	scanf("%d %d %d", &n, &m, &delta);
	for (int i = 0; i < n; i++) {
		int k = 5000;
		// scanf("%d", &k);
		while (k--) {
			int x = rand() % m + 1;
			// scanf("%d", &x);
			val[i][x]++;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = m; j >= 1; j--) {
			graph[i][j].push_back(pack(i, j - 1));
			if (j >= delta) {
				graph[i][j].push_back(pack(2003, j - delta));
			}
			graph[2003][j].push_back(pack(i, j));
		}
	}
	memset(f, -1, sizeof f);
	printf("%d", dfs(2003, m));
}