oj.uz

Submission #151802

# Submission time Handle Problem Language Result Execution time Memory
151802 2019-09-04T17:59:18 Z qkxwsm Wombats (IOI13_wombats) C++14
Compilation error
 0 ms 0 KB 
// #include "wombats.h"
#include "grader.h"
#include <bits/stdc++.h>

using namespace std;

template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 5013
#define MAXM 213
#define DIP 1024

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef array<array<int, MAXM>, MAXM> arr;

int N, M;
int H[MAXN][MAXM], V[MAXN][MAXM];
int pref[2][MAXM], opt[MAXM][MAXM];
map<int, arr> seg;

int cost(bool flag, int L, int R)
{
	if (R < L)
	{
		swap(L, R);
	}
	return pref[flag][R] - pref[flag][L];
}
arr base(int idx)
{
	arr res;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < M; j++)
		{
			res[i][j] = INF;
		}
	}
	pref[0][0] = 0;
	pref[1][0] = 0;
	for (int j = 0; j < M - 1; j++)
	{
		pref[0][j + 1] = pref[0][j] + H[idx][j];
		pref[1][j + 1] = pref[1][j] + H[idx + 1][j];
	}
	for (int i = 0; i < M; i++)
	{
		opt[i][M] = M - 1;
		for (int j = M - 1; j >= 0; j--)
		{
			for (int k = (i ? opt[i - 1][j] : 0); k <= opt[i][j + 1]; k++)
			{
				int cur = cost(0, i, k) + cost(1, k, j) + V[idx][k];
				if (cur < res[i][j])
				{
					opt[i][j] = k;
					res[i][j] = cur;
				}
			}
		}
	}
	// cerr << "moo\n";
	// for (int i = 0; i < M; i++)
	// {
	// 	for (int j = 0; j < M; j++)
	// 	{
	// 		cerr << res[i][j] << ' ';
	// 	}
	// 	cerr << endl;
	// }
	return res;
}
arr comb(arr lt, arr rt)
{
	arr res;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < M; j++)
		{
			res[i][j] = INF;
		}
	}
	for (int i = 0; i < M; i++)
	{
		opt[i][M] = M - 1;
		for (int j = M - 1; j >= 0; j--)
		{
			for (int k = (i ? opt[i - 1][j] : 0); k <= opt[i][j + 1]; k++)
			{
				int cur = lt[i][k] + rt[k][j];
				if (cur < res[i][j])
				{
					res[i][j] = cur;
					opt[i][j] = k;
				}
			}
		}
	}
	return res;
}
void build(int w, int L, int R)
{
	if (L == R)
	{
		seg[w] = base(L);
		return;
	}
	int mid = (L + R) >> 1;
	build(w << 1, L, mid);
	seg[w] = seg[w << 1];
	if ((w << 1) > DIP)
	{
		seg.erase(w << 1);
	}
	build(w << 1 | 1, mid + 1, R);
	seg[w] = comb(seg[w], seg[w << 1 | 1]);
	if ((w << 1 | 1) > DIP)
	{
		seg.erase(w << 1 | 1);
	}
}
void init(int R, int C, int h[5000][200], int v[5000][200])
{
	for (int i = 0; i < MAXN; i++)
	{
		for (int j = 0; j < MAXM; j++)
		{
			H[i][j] = INF;
			V[i][j] = INF;
		}
	}
	N = R; M = C;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C - 1; j++)
		{
			H[i][j] = h[i][j];
		}
	}
	for (int i = 0; i < R - 1; i++)
	{
		for (int j = 0; j < C; j++)
		{
			V[i][j] = v[i][j];
		}
	}
	build(1, 0, N - 2);
}

void update(int w, int L, int R, int idx)
{
	if ((idx < L || idx > R) && (w <= DIP))
	{
		return;
	}
	if (L == R)
	{
		// cerr << "pull " << L << endl;
		seg[w] = base(L);
		return;
	}
	int mid = (L + R) >> 1;
	update(w << 1, L, mid, idx);
	seg[w] = seg[w << 1];
	if ((w << 1) > DIP)
	{
		seg.erase(w << 1);
	}
	update(w << 1 | 1, mid + 1, R, idx);
	seg[w] = comb(seg[w], seg[w << 1 | 1]);
	if ((w << 1 | 1) > DIP)
	{
		seg.erase(w << 1 | 1);
	}
}

void changeH(int P, int Q, int W)
{
	/* ... */
	H[P][Q] = W;
	if (P < N - 1) update(1, 0, N - 2, P);
	if (P > 0) update(1, 0, N - 2, P - 1);
}

void changeV(int P, int Q, int W)
{
	/* ... */
	V[P][Q] = W;
	update(1, 0, N - 2, P);
}

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

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp:2:10: fatal error: grader.h: No such file or directory
 #include "grader.h"
          ^~~~~~~~~~
compilation terminated.