oj.uz

Submission #151803

# Submission time Handle Problem Language Result Execution time Memory
151803 2019-09-04T18:00:19 Z qkxwsm Wombats (IOI13_wombats) C++14
100 / 100
 12889 ms 212860 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;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1968 ms 197828 KB Output is correct
2 Correct 1976 ms 197816 KB Output is correct
3 Correct 2044 ms 200124 KB Output is correct
4 Correct 2015 ms 197808 KB Output is correct
5 Correct 1977 ms 197736 KB Output is correct
6 Correct 10 ms 8952 KB Output is correct
7 Correct 10 ms 8824 KB Output is correct
8 Correct 10 ms 8952 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8952 KB Output is correct
2 Correct 10 ms 8824 KB Output is correct
3 Correct 10 ms 8824 KB Output is correct
4 Correct 19 ms 16504 KB Output is correct
5 Correct 19 ms 16504 KB Output is correct
6 Correct 19 ms 16504 KB Output is correct
7 Correct 19 ms 16504 KB Output is correct
8 Correct 21 ms 16120 KB Output is correct
9 Correct 19 ms 16120 KB Output is correct
10 Correct 22 ms 16504 KB Output is correct
11 Correct 99 ms 18808 KB Output is correct
12 Correct 19 ms 16504 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 45688 KB Output is correct
2 Correct 161 ms 45688 KB Output is correct
3 Correct 314 ms 46100 KB Output is correct
4 Correct 194 ms 46072 KB Output is correct
5 Correct 237 ms 46072 KB Output is correct
6 Correct 10 ms 8824 KB Output is correct
7 Correct 12 ms 8900 KB Output is correct
8 Correct 11 ms 8876 KB Output is correct
9 Correct 905 ms 46100 KB Output is correct
10 Correct 11 ms 9592 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2554 ms 201836 KB Output is correct
2 Correct 1995 ms 201688 KB Output is correct
3 Correct 2613 ms 201740 KB Output is correct
4 Correct 2591 ms 203116 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 45944 KB Output is correct
2 Correct 167 ms 45736 KB Output is correct
3 Correct 306 ms 46072 KB Output is correct
4 Correct 190 ms 46200 KB Output is correct
5 Correct 250 ms 45984 KB Output is correct
6 Correct 2589 ms 201804 KB Output is correct
7 Correct 1947 ms 201740 KB Output is correct
8 Correct 2547 ms 201804 KB Output is correct
9 Correct 2608 ms 203016 KB Output is correct
10 Correct 1993 ms 197864 KB Output is correct
11 Correct 1963 ms 197868 KB Output is correct
12 Correct 2053 ms 200252 KB Output is correct
13 Correct 2011 ms 197824 KB Output is correct
14 Correct 1977 ms 197692 KB Output is correct
15 Correct 10 ms 8824 KB Output is correct
16 Correct 10 ms 8952 KB Output is correct
17 Correct 10 ms 8952 KB Output is correct
18 Correct 19 ms 16504 KB Output is correct
19 Correct 18 ms 16500 KB Output is correct
20 Correct 19 ms 16504 KB Output is correct
21 Correct 19 ms 16504 KB Output is correct
22 Correct 18 ms 16120 KB Output is correct
23 Correct 19 ms 16120 KB Output is correct
24 Correct 18 ms 16504 KB Output is correct
25 Correct 97 ms 18936 KB Output is correct
26 Correct 19 ms 16504 KB Output is correct
27 Correct 911 ms 46172 KB Output is correct
28 Correct 5216 ms 205960 KB Output is correct
29 Correct 4417 ms 204328 KB Output is correct
30 Correct 4506 ms 204144 KB Output is correct
31 Correct 4890 ms 207616 KB Output is correct
32 Correct 11 ms 9592 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 45872 KB Output is correct
2 Correct 165 ms 45692 KB Output is correct
3 Correct 328 ms 46100 KB Output is correct
4 Correct 187 ms 46072 KB Output is correct
5 Correct 236 ms 46072 KB Output is correct
6 Correct 2556 ms 201804 KB Output is correct
7 Correct 1972 ms 201872 KB Output is correct
8 Correct 2632 ms 201776 KB Output is correct
9 Correct 2519 ms 203160 KB Output is correct
10 Correct 1974 ms 197984 KB Output is correct
11 Correct 1978 ms 197884 KB Output is correct
12 Correct 2075 ms 200508 KB Output is correct
13 Correct 1994 ms 197856 KB Output is correct
14 Correct 1984 ms 197784 KB Output is correct
15 Correct 4137 ms 211812 KB Output is correct
16 Correct 12889 ms 212860 KB Output is correct
17 Correct 10 ms 8824 KB Output is correct
18 Correct 10 ms 8824 KB Output is correct
19 Correct 12 ms 8920 KB Output is correct
20 Correct 19 ms 16504 KB Output is correct
21 Correct 19 ms 16504 KB Output is correct
22 Correct 21 ms 16504 KB Output is correct
23 Correct 21 ms 16504 KB Output is correct
24 Correct 18 ms 16120 KB Output is correct
25 Correct 21 ms 16120 KB Output is correct
26 Correct 21 ms 16504 KB Output is correct
27 Correct 102 ms 18808 KB Output is correct
28 Correct 19 ms 16632 KB Output is correct
29 Correct 983 ms 46104 KB Output is correct
30 Correct 5275 ms 205996 KB Output is correct
31 Correct 12066 ms 210340 KB Output is correct
32 Correct 11854 ms 210372 KB Output is correct
33 Correct 4409 ms 204268 KB Output is correct
34 Correct 10551 ms 208352 KB Output is correct
35 Correct 4486 ms 204228 KB Output is correct
36 Correct 10752 ms 208496 KB Output is correct
37 Correct 4907 ms 207640 KB Output is correct
38 Correct 11360 ms 210984 KB Output is correct
39 Correct 11 ms 9592 KB Output is correct
40 Correct 11105 ms 208584 KB Output is correct