oj.uz

Submission #316349

# Submission time Handle Problem Language Result Execution time Memory
316349 2020-10-26T04:52:10 Z VROOM_VARUN Wombats (IOI13_wombats) C++14
100 / 100
 4990 ms 184748 KB 
/*
ID: varunra2
LANG: C++
TASK: wombat
*/

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

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n, m;

bool sub1 = false;
bool sub23 = false;
bool sub4 = false;

int hsh(int i, int j) { return i * m + j; }

PII unhsh(int h) { return MP(h / m, h % m); }

VVI h(5001, VI(201, INF));
VVI v(5001, VI(201));

const int block = 10;
const int c = 200;

void pr(int dp[c][c]) {
  rep(i, 0, m) {
    rep(j, 0, m) { cout << dp[i][j] << " "; }
    cout << '\n';
  }
  cout << '\n';
}

struct node {
  int dp[c][c];
  VI opt;

  void calcLeaf(int ind) {
    for (int i = 0; i < c; i++) {
      for (int j = 0; j < c; j++) {
        dp[i][j] = INF;
      }
    }
    for (int i = 0; i < c; i++) {
      dp[i][i] = 0;
      for (int j = ind * block; j < (ind + 1) * block; j++) {
        for (int k = 1; k < c; k++) {
          dp[i][k] = min(dp[i][k], dp[i][k - 1] + h[j][k - 1]);
        }
        for (int k = c - 1; k >= 1; k--) {
          dp[i][k - 1] = min(dp[i][k - 1], dp[i][k] + h[j][k - 1]);
        }
        for (int k = 0; k < c; k++) {
          dp[i][k] += v[j][k];
        }
      }
    }
    // cout << ind << '\n';
    // pr(dp);
  }

} segtree[1024];

void comb(node& a, node& l, node& r) {
  a.opt.assign(c + 1, 0);
  a.opt[c] = c - 1;
  for (int i = 0; i < c; i++) {
    for (int j = c - 1; j >= 0; j--) {
      PII ret = MP(INF, 0);
      for (int k = a.opt[j]; k <= a.opt[j + 1]; k++) {
        ret = min(ret, MP(l.dp[i][k] + r.dp[k][j], -k));
      }
      a.dp[i][j] = ret.x;
      a.opt[j] = -ret.y;
    }
  }
}

void upd(int l, int r, int tl, int tr, int node) {
  if (l > tr or r < tl) return;
  if (l == r) {
    segtree[node].calcLeaf(l);
    return;
  }
  int mid = (l + r) / 2;
  upd(l, mid, tl, tr, 2 * node + 1);
  upd(mid + 1, r, tl, tr, 2 * node + 2);
  comb(segtree[node], segtree[2 * node + 1], segtree[2 * node + 2]);
}

const int siz = 500;

void upd(int l, int r) { upd(0, siz - 1, l, r, 0); }

void init(int R, int C, int H[5000][200], int V[5000][200]) {
  n = R;
  m = C;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m - 1; j++) {
      h[i][j] = H[i][j];
    }
  }

  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < m; j++) {
      v[i][j] = V[i][j];
    }
  }

  upd(0, siz - 1);
  // pr(segtree[0].dp);
}

void changeV(int p, int q, int w) {
  v[p][q] = w;
  upd(p / block, p / block);
}

void changeH(int p, int q, int w) {
  h[p][q] = w;
  upd(p / block, p / block);
}

int escape(int a, int b) { return segtree[0].dp[a][b]; }

// int main() {
// #ifndef ONLINE_JUDGE
//   freopen("wombat.in", "r", stdin);
//   freopen("wombat.out", "w", stdout);
// #endif
//   cin.sync_with_stdio(0);
//   cin.tie(0);

//   int r, c;
//   int h[5000][200];
//   int v[5000][200];

//   cin >> r >> c;

//   rep(i, 0, r) rep(j, 0, c - 1) cin >> h[i][j];
//   rep(i, 0, r - 1) rep(j, 0, c) cin >> v[i][j];

//   init(r, c, h, v);
//   debug("done");
//   int q;
//   cin >> q;

//   while (q--) {
//     int type;
//     cin >> type;
//     if (type == 0) {
//       int a, b;
//       cin >> a >> b;
//       cout << escape(a, b) << '\n';
//     } else if (type == 1) {
//       int p, q, w;
//       cin >> p >> q >> w;
//       changeV(p, q, w);
//     } else {
//       int p, q, w;
//       cin >> p >> q >> w;
//       changeH(p, q, w);
//     }
//     debug("done", type);
//   }

//   return 0;
// }

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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4521 ms 169596 KB Output is correct
2 Correct 4549 ms 169472 KB Output is correct
3 Correct 4643 ms 171756 KB Output is correct
4 Correct 4572 ms 169676 KB Output is correct
5 Correct 4533 ms 169720 KB Output is correct
6 Correct 1614 ms 165572 KB Output is correct
7 Correct 1617 ms 165584 KB Output is correct
8 Correct 1602 ms 165624 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1625 ms 165592 KB Output is correct
2 Correct 1610 ms 165472 KB Output is correct
3 Correct 1607 ms 165496 KB Output is correct
4 Correct 1611 ms 165748 KB Output is correct
5 Correct 1604 ms 165624 KB Output is correct
6 Correct 1602 ms 165600 KB Output is correct
7 Correct 1599 ms 165628 KB Output is correct
8 Correct 1609 ms 165752 KB Output is correct
9 Correct 1607 ms 165564 KB Output is correct
10 Correct 1597 ms 165548 KB Output is correct
11 Correct 1691 ms 167228 KB Output is correct
12 Correct 1603 ms 165756 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2189 ms 166008 KB Output is correct
2 Correct 2186 ms 165964 KB Output is correct
3 Correct 2222 ms 165944 KB Output is correct
4 Correct 2186 ms 165880 KB Output is correct
5 Correct 2187 ms 166036 KB Output is correct
6 Correct 1591 ms 165516 KB Output is correct
7 Correct 1593 ms 165496 KB Output is correct
8 Correct 1605 ms 165624 KB Output is correct
9 Correct 4580 ms 165772 KB Output is correct
10 Correct 1613 ms 165624 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4553 ms 173724 KB Output is correct
2 Correct 4571 ms 173508 KB Output is correct
3 Correct 4578 ms 173432 KB Output is correct
4 Correct 4622 ms 174764 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2190 ms 165964 KB Output is correct
2 Correct 2201 ms 165768 KB Output is correct
3 Correct 2197 ms 165880 KB Output is correct
4 Correct 2210 ms 166008 KB Output is correct
5 Correct 2194 ms 166136 KB Output is correct
6 Correct 4532 ms 173428 KB Output is correct
7 Correct 4570 ms 173560 KB Output is correct
8 Correct 4586 ms 173576 KB Output is correct
9 Correct 4622 ms 174868 KB Output is correct
10 Correct 4506 ms 169516 KB Output is correct
11 Correct 4551 ms 169524 KB Output is correct
12 Correct 4648 ms 171868 KB Output is correct
13 Correct 4577 ms 169568 KB Output is correct
14 Correct 4562 ms 169592 KB Output is correct
15 Correct 1611 ms 165496 KB Output is correct
16 Correct 1616 ms 165496 KB Output is correct
17 Correct 1604 ms 165624 KB Output is correct
18 Correct 1597 ms 165548 KB Output is correct
19 Correct 1593 ms 165624 KB Output is correct
20 Correct 1612 ms 165816 KB Output is correct
21 Correct 1598 ms 165636 KB Output is correct
22 Correct 1595 ms 165536 KB Output is correct
23 Correct 1611 ms 165532 KB Output is correct
24 Correct 1601 ms 165628 KB Output is correct
25 Correct 1698 ms 167476 KB Output is correct
26 Correct 1609 ms 165464 KB Output is correct
27 Correct 4497 ms 165800 KB Output is correct
28 Correct 4685 ms 175180 KB Output is correct
29 Correct 4700 ms 175932 KB Output is correct
30 Correct 4748 ms 175944 KB Output is correct
31 Correct 4768 ms 179264 KB Output is correct
32 Correct 1609 ms 165540 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2202 ms 165752 KB Output is correct
2 Correct 2184 ms 165880 KB Output is correct
3 Correct 2212 ms 165900 KB Output is correct
4 Correct 2189 ms 165752 KB Output is correct
5 Correct 2194 ms 166060 KB Output is correct
6 Correct 4561 ms 173688 KB Output is correct
7 Correct 4564 ms 173560 KB Output is correct
8 Correct 4586 ms 173688 KB Output is correct
9 Correct 4601 ms 174804 KB Output is correct
10 Correct 4515 ms 169592 KB Output is correct
11 Correct 4545 ms 169452 KB Output is correct
12 Correct 4603 ms 171952 KB Output is correct
13 Correct 4569 ms 169464 KB Output is correct
14 Correct 4559 ms 169476 KB Output is correct
15 Correct 1886 ms 174328 KB Output is correct
16 Correct 4881 ms 184748 KB Output is correct
17 Correct 1602 ms 165772 KB Output is correct
18 Correct 1593 ms 165752 KB Output is correct
19 Correct 1611 ms 165712 KB Output is correct
20 Correct 1596 ms 165888 KB Output is correct
21 Correct 1609 ms 165752 KB Output is correct
22 Correct 1606 ms 165660 KB Output is correct
23 Correct 1602 ms 165800 KB Output is correct
24 Correct 1614 ms 165708 KB Output is correct
25 Correct 1600 ms 165600 KB Output is correct
26 Correct 1612 ms 165584 KB Output is correct
27 Correct 1686 ms 168184 KB Output is correct
28 Correct 1612 ms 165656 KB Output is correct
29 Correct 4497 ms 165768 KB Output is correct
30 Correct 4702 ms 177912 KB Output is correct
31 Correct 4460 ms 181772 KB Output is correct
32 Correct 4484 ms 181736 KB Output is correct
33 Correct 4676 ms 175736 KB Output is correct
34 Correct 4762 ms 179756 KB Output is correct
35 Correct 4700 ms 175736 KB Output is correct
36 Correct 4833 ms 179820 KB Output is correct
37 Correct 4742 ms 179228 KB Output is correct
38 Correct 4649 ms 182416 KB Output is correct
39 Correct 1611 ms 165496 KB Output is correct
40 Correct 4990 ms 179876 KB Output is correct