oj.uz

Submission #962628

# Submission time Handle Problem Language Result Execution time Memory
962628 2024-04-14T04:20:41 Z nguyentunglam Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 168632 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 (s * 2 > M || r - l <= 10) {
    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 = c - 1; i >= 0; i--) for(int j = 0; j < c; j++) {
    T[s][i][j] = 2e9;
    int st = j - 1 >= 0 ? opt[i][j - 1] : 0;
    int ed = i + 1 < c ? opt[i + 1][j] : c - 1;
    for(int k = st; k <= ed; 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 95068 KB Output is correct
2 Correct 13 ms 94812 KB Output is correct
3 Correct 64 ms 96432 KB Output is correct
4 Correct 13 ms 94808 KB Output is correct
5 Correct 12 ms 95068 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 54 ms 11688 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 13064 KB Output is correct
2 Correct 119 ms 13316 KB Output is correct
3 Correct 137 ms 13056 KB Output is correct
4 Correct 137 ms 13148 KB Output is correct
5 Correct 133 ms 13148 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 377 ms 13072 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 99420 KB Output is correct
2 Correct 15 ms 99420 KB Output is correct
3 Correct 17 ms 99312 KB Output is correct
4 Correct 49 ms 100180 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 13136 KB Output is correct
2 Correct 118 ms 13084 KB Output is correct
3 Correct 132 ms 13072 KB Output is correct
4 Correct 136 ms 13392 KB Output is correct
5 Correct 128 ms 12984 KB Output is correct
6 Correct 15 ms 99420 KB Output is correct
7 Correct 16 ms 99420 KB Output is correct
8 Correct 16 ms 99416 KB Output is correct
9 Correct 42 ms 100256 KB Output is correct
10 Correct 13 ms 94836 KB Output is correct
11 Correct 13 ms 95064 KB Output is correct
12 Correct 63 ms 96552 KB Output is correct
13 Correct 13 ms 95068 KB Output is correct
14 Correct 13 ms 94876 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4796 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 3 ms 10720 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 2 ms 10588 KB Output is correct
23 Correct 2 ms 10588 KB Output is correct
24 Correct 2 ms 10588 KB Output is correct
25 Correct 58 ms 11516 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 378 ms 13072 KB Output is correct
28 Correct 6255 ms 140644 KB Output is correct
29 Correct 4615 ms 143776 KB Output is correct
30 Correct 4766 ms 143944 KB Output is correct
31 Correct 6040 ms 145812 KB Output is correct
32 Correct 1 ms 8632 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 13140 KB Output is correct
2 Correct 118 ms 13136 KB Output is correct
3 Correct 131 ms 13148 KB Output is correct
4 Correct 131 ms 13140 KB Output is correct
5 Correct 135 ms 13148 KB Output is correct
6 Correct 18 ms 99416 KB Output is correct
7 Correct 15 ms 99416 KB Output is correct
8 Correct 19 ms 99420 KB Output is correct
9 Correct 42 ms 100188 KB Output is correct
10 Correct 14 ms 95068 KB Output is correct
11 Correct 13 ms 94916 KB Output is correct
12 Correct 69 ms 96596 KB Output is correct
13 Correct 13 ms 95068 KB Output is correct
14 Correct 13 ms 94840 KB Output is correct
15 Execution timed out 20013 ms 168632 KB Time limit exceeded
16 Halted 0 ms 0 KB -