oj.uz

Submission #962627

# Submission time Handle Problem Language Result Execution time Memory
962627 2024-04-14T04:17:07 Z nguyentunglam Wombats (IOI13_wombats) C++17
28 / 100
 3656 ms 42700 KB 
#include<bits/stdc++.h>
using namespace std;
#include "wombats.h"

const int M = 1000;

int T[M + 10][200][200];

int h[5010][210], v[5010][210];

int f[210][210], opt[210][210];

int r, c;

void calc (int l, int r) {
  for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) f[i][j] = (i == j ? 0 : 1e9);
  for(int row = l; row <= r; row++) {
    if (row != l) {
      for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) {
        f[i][j] += v[row - 1][j];
      }
    }
    for(int i = 0; i < c; i++) {
      for(int j = 1; j < c; j++) f[i][j] = min(f[i][j], f[i][j - 1] + h[row][j - 1]);
      for(int j = c - 2; j >= 0; j--) f[i][j] = min(f[i][j], f[i][j + 1] + h[row][j]);
    }
  }
}

void up (int s, int l, int r, int pos) {
//  if (s == 2) cout << l << " " << r << endl;
  if (l == r) {
    calc(l, r);
    for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) T[s][i][j] = f[i][j];
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) up(s << 1, l, mid, pos);
  else up(s << 1 | 1, mid + 1, r, pos);

//  for(int i = 0; i < c; i++) {
//    T[s][i][i] = 2e9;
//    for(int j = 0; j < c; j++) {
//      int cost = T[s << 1][i][j] + v[mid][j] + T[s << 1 | 1][j][i];
//      if (T[s][i][i] > cost) {
//        T[s][i][i] = cost;
//        opt[i][i] = j;
//      }
//    }
//  }
  for(int i = c - 1; i >= 0; i--) for(int j = 0; j < c; j++) {
    T[s][i][j] = 2e9;
    for(int k = 0; k < c; k++) {
      int cost = T[s << 1][i][k] + v[mid][k] + T[s << 1 | 1][k][j];
      if (T[s][i][j] > cost) {
        T[s][i][j] = cost;
        opt[i][j] = k;
      }
    }
  }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
  r = R;
  c = C;
  for(int i = 0; i < r; i++) for(int j = 0; j + 1 < c; j++) h[i][j] = H[i][j];
  for(int i = 0; i + 1 < r; i++) for(int j = 0; j < c; j++) v[i][j] = V[i][j];
  for(int i = 0; i < r; i++) up(1, 0, r - 1, i);
//  cout << T[2][2][1];
//  exit(0);
//  for(int i = 0; i < r; i++) {
//    for(int j = 0; j + 1 < c; j++) cout << h[i][j] << " ";
//    cout << endl;
//  }
//
//  for(int i = 0; i + 1 < r; i++) {
//    for(int j = 0; j < c; j++) cout << v[i][j] << " ";
//    cout << endl;
//  }
}

void changeH(int P, int Q, int W) {
  h[P][Q] = W;
  up(1, 0, r - 1, P);
}

void changeV(int P, int Q, int W) {
  v[P][Q] = W;
  up(1, 0, r - 1, P);
}

int escape(int V1, int V2) {
  return T[1][V1][V2];
}

#ifdef ngu

#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

static int H[5000][200];
static int V[5000][200];

int main() {
  freopen ("task.out", "w", stdout);
	int R, C, E, P, Q, W, V1, V2, event, i, j;
	int res;
	FILE *f = fopen("task.inp", "r");
	if (!f)
		fail("Failed to open input file.");

	res = fscanf(f, "%d%d", &R, &C);
    for (i = 0; i < R; ++i)
        for (j = 0; j < C-1; ++j)
            res = fscanf(f, "%d", &H[i][j]);
    for (i = 0; i < R-1; ++i)
        for (j = 0; j < C; ++j)
            res = fscanf(f, "%d", &V[i][j]);

    init(R, C, H, V);

	res = fscanf(f, "%d", &E);
	for (i = 0; i < E; i++) {
		res = fscanf(f, "%d", &event);
        if (event == 1) {
            res = fscanf(f, "%d%d%d", &P, &Q, &W);
            changeH(P, Q, W);
        } else if (event == 2) {
            res = fscanf(f, "%d%d%d", &P, &Q, &W);
            changeV(P, Q, W);
        } else if (event == 3) {
            res = fscanf(f, "%d%d", &V1, &V2);
            cout << escape(V1, V2) << endl;
//            printf("%d\n", escape(V1, V2));
        } else
            fail("Invalid event type.");
	}

	fclose(f);
	return 0;
}
#endif // ngu

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'void up(int, int, int, int)':
wombats.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 21596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6508 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 5 ms 16812 KB Output is correct
6 Correct 7 ms 16736 KB Output is correct
7 Correct 3 ms 16728 KB Output is correct
8 Correct 3 ms 14680 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 60 ms 17756 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1387 ms 42460 KB Output is correct
2 Correct 1048 ms 42508 KB Output is correct
3 Correct 1446 ms 42404 KB Output is correct
4 Correct 1412 ms 42460 KB Output is correct
5 Correct 1372 ms 42408 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 3656 ms 42568 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 34132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1464 ms 42460 KB Output is correct
2 Correct 1051 ms 42408 KB Output is correct
3 Correct 1351 ms 42300 KB Output is correct
4 Correct 1396 ms 42384 KB Output is correct
5 Correct 1399 ms 42408 KB Output is correct
6 Runtime error 24 ms 34136 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1376 ms 42324 KB Output is correct
2 Correct 1101 ms 42296 KB Output is correct
3 Correct 1417 ms 42456 KB Output is correct
4 Correct 1372 ms 42700 KB Output is correct
5 Correct 1371 ms 42408 KB Output is correct
6 Runtime error 19 ms 34136 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -