Submission #399076

#	Time	Username	Problem	Language	Result	Execution time	Memory
399076		prvocislo	Wombats (IOI13_wombats)	C++17	28 / 100	5264 ms	38208 KiB

wombats

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include "wombats.h"
typedef long long ll;
using namespace std;

int r, c; const int inf = 1e9 + 79, maxr = 5001, maxc = 201;
int r2 = 1;
vector<vector<int> > h(maxr, vector<int>(maxc, inf)), v(maxr, vector<int>(maxc, 0)); // h -> cesta z predosleho stlpca, v -> cesta z predosleho riadku
class node
{
public:
	int l, r;
	vector<vector<int> > dp;
	node() : dp(vector<vector<int> >(c, vector<int>(c, 0))) {}
	node(int rw) : dp(vector<vector<int> >(c, vector<int>(c, 0))), l(rw), r(rw) {
		for (int i = 0; i < c; i++) for (int j = 0; j < c; j++) {
			dp[i][j] = v[rw][i];
			for (int k = min(i, j) + 1; k <= max(i, j); k++) dp[i][j] += h[rw][k], dp[i][j] = min(dp[i][j], inf);
		}
	}
};
void merge(const node &l, const node &r, node& res)
{
	res.l = l.l, res.r = r.r;
	for (int i = 0; i < c; i++) for (int j = 0; j < c; j++) res.dp[i][j] = inf;
	for (int i = 0; i < c; i++) for (int j = 0; j < c; j++) for (int k = 0; k < c; k++)
		res.dp[i][j] = min(res.dp[i][j], l.dp[i][k] + r.dp[k][j]);
}
vector<node> st; // musi to byt presne r aby sme vedeli skoncit v y2
void update(int i)
{
	st[i + r2] = node(i); i += r2;
	for (i = (i >> 1); i > 0; i >>= 1) 
		merge(st[(i << 1)], st[(i << 1) | 1], st[i]);
}
int escape(int y1, int y2) {
	return st[1].dp[y1][y2];
}
void changeH(int x, int y, int w) {
	h[x][y + 1] = w;
	update(x);
}
void changeV(int x, int y, int w) {
	v[x + 1][y] = w;
	update(x + 1);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R, c = C;
	while (r2 < r) r2 <<= 1;
	st.resize(r2 * 2);
	for (int i = 0; i < r; i++) for (int j = 0; j < c - 1; j++)
		h[i][j + 1] = H[i][j];
	for (int i = 0; i < r - 1; i++) for (int j = 0; j < c; j++)
		v[i + 1][j] = V[i][j];
	for (int i = 0; i < r2; i++) st[i + r2] = node(i);
	for (int i = r2 - 1; i > 0; i--) merge(st[i << 1], st[(i << 1) | 1], st[i]);
}

Compilation message (stderr)

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 constructor 'node::node(int)':
wombats.cpp:18:23: warning: 'node::dp' will be initialized after [-Wreorder]
   18 |  vector<vector<int> > dp;
      |                       ^~
wombats.cpp:17:6: warning:   'int node::l' [-Wreorder]
   17 |  int l, r;
      |      ^
wombats.cpp:20:2: warning:   when initialized here [-Wreorder]
   20 |  node(int rw) : dp(vector<vector<int> >(c, vector<int>(c, 0))), l(rw), r(rw) {
      |  ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24