Submission #68057057

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
int main(void) {
  int H, W;
  int** A;
  int* P;
  int64_t** required;
  int i, j;
  if (scanf("%d%d", &H, &W) != 2) return 1;
  A = malloc(sizeof(*A) * H);
  if (A == NULL) return 2;
  A[0] = malloc(sizeof(**A) * H * W);
  if (A[0] == NULL) return 2;
  for (i = 1; i < H; i++) {
    A[i] = A[0] + W * i;
  }
  for (i = 0; i < H; i++) {
    for (j = 0; j < W; j++) {
      if (scanf("%d", &A[i][j]) != 1) return 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int main(void) {
	int H, W;
	int** A;
	int* P;
	int64_t** required;
	int i, j;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	A = malloc(sizeof(*A) * H);
	if (A == NULL) return 2;
	A[0] = malloc(sizeof(**A) * H * W);
	if (A[0] == NULL) return 2;
	for (i = 1; i < H; i++) {
		A[i] = A[0] + W * i;
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (scanf("%d", &A[i][j]) != 1) return 1;
		}
	}
	P = malloc(sizeof(*P) * (H + W - 1));
	if (P == NULL) return 2;
	required = malloc(sizeof(*required) * H);
	if (required == NULL) return 2;
	required[0] = malloc(sizeof(**required) * H * W);
	if (required[0] == NULL) return 2;
	for (i = 1; i < H; i++) {
		required[i] = required[0] + W * i;
	}
	for (i = 0; i < H + W - 1; i++) {
		if (scanf("%d", &P[i]) != 1) return 1;
	}

	for (i = H - 1; i >= 0; i--) {
		for (j = W - 1; j >= 0; j--) {
			int64_t cur_req = INT64_MAX;
			if (i == H - 1 && j == W - 1) cur_req = 0;
			if (i + 1 < H && required[i + 1][j] < cur_req) cur_req = required[i + 1][j];
			if (j + 1 < W && required[i][j + 1] < cur_req) cur_req = required[i][j + 1];
			cur_req += P[i + j];
			cur_req -= A[i][j];
			if (cur_req < 0) cur_req = 0;
			required[i][j] = cur_req;
		}
	}
	printf("%" PRId64 "\n", required[0][0]);

	free(required[0]);
	free(required);
	free(P);
	free(A[0]);
	free(A);
	return 0;
}

Submission Info

Judge Result