Submission #870969

#	Time	Username	Problem	Language	Result	Execution time	Memory
870969		rainboy	Restore Array (RMI19_restore)	C11	100 / 100	394 ms	856 KiB

restore

#include <stdio.h>
#include <string.h>

#define N	5000
#define M	20000

int main() {
	static int ii[M], jj[M], ww[M], dd[N + 1], dd_[N + 1];
	int n, m, m_, h, i, j, k, c, d;

	scanf("%d%d", &n, &m);
	m_ = 0;
	for (i = 0; i < n; i++) {
		ii[m_] = i, jj[m_] = i + 1, ww[m_] = 1, m_++;
		ii[m_] = i + 1, jj[m_] = i, ww[m_] = 0, m_++;
	}
	while (m--) {
		scanf("%d%d%d%d", &i, &j, &k, &c), j++;
		if (c == 0)
			ii[m_] = i, jj[m_] = j, ww[m_] = j - i - k, m_++;
		else
			ii[m_] = j, jj[m_] = i, ww[m_] = -(j - i + 1 - k), m_++;
	}
	m = m_;
	for (k = 0; k <= n; k++) {
		memcpy(dd_, dd, (n + 1) * sizeof *dd_);
		for (h = 0; h < m; h++) {
			i = ii[h], j = jj[h];
			if (dd[j] > (d = dd_[i] + ww[h])) {
				if (k == n) {
					printf("-1\n");
					return 0;
				}
				dd[j] = d;
			}
		}
	}
	for (i = 0; i < n; i++)
		printf("%d ", dd[i + 1] - dd[i]);
	printf("\n");
	return 0;
}

Compilation message (stderr)

restore.c: In function 'main':
restore.c:11:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
restore.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d%d%d%d", &i, &j, &k, &c), j++;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55