oj.uz

Submission #280369

# Submission time Handle Problem Language Result Execution time Memory
280369 2020-08-22T16:57:49 Z _7_7_ Wombats (IOI13_wombats) C++14
43 / 100
 4293 ms 96872 KB 
#include "wombats.h"
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;                                   	
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 1012;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;


int h[5000][200], v[5000][200], n = 5000, m = 200, L = 20, bl = n / L, opt[200][200];
int t[2000][200][200];
 
void update (int pos, int v = 1, int tl = 0, int tr = bl - 1) {
	if (tl == tr) {
		for (int j = 0; j < m; ++j)
			for (int x = 0; x < m; ++x)
				t[v][j][x] = inf;
		
		for (int j = 0; j < m; ++j) {
			t[v][j][j] = 0;
			for (int i = tl*L; i < (tl + 1)*L ; ++i) {
				for (int x = 0; x + 1 < m; ++x)
					t[v][j][x + 1] = min(t[v][j][x + 1], t[v][j][x] + h[i][x]);
				
				for (int x = m - 1; x > 0; --x)
					t[v][j][x - 1] = min(t[v][j][x - 1], t[v][j][x] + h[i][x - 1]);

				for (int x = 0; x < m; ++x) 
					t[v][j][x] += ::v[i][x]; 				
			}
		}

		return;
	}

	int tm = (tl + tr) >> 1;
	if (pos <= tm)
		update(pos, v << 1, tl, tm);
	else
		update(pos, v << 1 | 1, tm + 1, tr);
	
	for (int i = 0; i < m; ++i)	
		for (int j = m - 1; j >= 0; --j) {
 			int optl = !i ? 0 : opt[i - 1][j], optr = j == m - 1 ? m - 1 : opt[i][j + 1];
//			int optl = 0, optr = m - 1;
			t[v][i][j] = inf*2;

			for (int x = optl; x <= optr; ++x)
				if (t[v][i][j] > t[v << 1][i][x] + t[v << 1 | 1][x][j]) {
					t[v][i][j] = t[v << 1][i][x] + t[v << 1 | 1][x][j];
					opt[i][j] = x;
				}
		}
}

void init(int r, int c, int H[5000][200], int V[5000][200]) {
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			h[i][j] = inf;
			v[i][j] = 0;
			if (i < r && j + 1 < c)
				h[i][j] = H[i][j];
			if (i + 1 < r && j < c)
				v[i][j] = V[i][j];
		}

	for (int i = 0; i < bl; ++i)
		update(i);
}
 
void changeH(int p, int q, int w) {
	h[p][q] = w;
	update(p / L);
}
 
void changeV(int p, int q, int w) {
	v[p][q] = w;
	update(p / L);
}
 
int escape(int a, int b) {
	return t[1][a][b];
}

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 3950 ms 90592 KB Output is correct
2 Correct 3802 ms 90436 KB Output is correct
3 Correct 3922 ms 91936 KB Output is correct
4 Correct 3835 ms 90608 KB Output is correct
5 Correct 4048 ms 90344 KB Output is correct
6 Correct 1255 ms 86520 KB Output is correct
7 Correct 1274 ms 86520 KB Output is correct
8 Correct 1266 ms 86552 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1288 ms 86536 KB Output is correct
2 Correct 1302 ms 86476 KB Output is correct
3 Correct 1287 ms 86524 KB Output is correct
4 Correct 1266 ms 86476 KB Output is correct
5 Incorrect 1260 ms 86724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1844 ms 86648 KB Output is correct
2 Correct 1847 ms 86680 KB Output is correct
3 Correct 1881 ms 86660 KB Output is correct
4 Correct 1861 ms 86652 KB Output is correct
5 Correct 1863 ms 86752 KB Output is correct
6 Correct 1272 ms 86604 KB Output is correct
7 Correct 1245 ms 86648 KB Output is correct
8 Correct 1299 ms 86584 KB Output is correct
9 Correct 4152 ms 86776 KB Output is correct
10 Correct 1386 ms 86480 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3897 ms 94464 KB Output is correct
2 Correct 3875 ms 94268 KB Output is correct
3 Correct 3905 ms 94448 KB Output is correct
4 Correct 4032 ms 95232 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1879 ms 86684 KB Output is correct
2 Correct 1964 ms 86744 KB Output is correct
3 Correct 1846 ms 86728 KB Output is correct
4 Correct 1855 ms 86720 KB Output is correct
5 Correct 1822 ms 86676 KB Output is correct
6 Correct 3874 ms 94456 KB Output is correct
7 Correct 3974 ms 94440 KB Output is correct
8 Correct 3920 ms 94300 KB Output is correct
9 Correct 4030 ms 95220 KB Output is correct
10 Correct 3866 ms 90444 KB Output is correct
11 Correct 4144 ms 90360 KB Output is correct
12 Correct 4166 ms 91960 KB Output is correct
13 Correct 4006 ms 90420 KB Output is correct
14 Correct 4216 ms 90420 KB Output is correct
15 Correct 1312 ms 86392 KB Output is correct
16 Correct 1306 ms 86388 KB Output is correct
17 Correct 1282 ms 86480 KB Output is correct
18 Correct 1315 ms 86512 KB Output is correct
19 Incorrect 1299 ms 86464 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1900 ms 86668 KB Output is correct
2 Correct 1851 ms 86696 KB Output is correct
3 Correct 1865 ms 86712 KB Output is correct
4 Correct 1910 ms 86784 KB Output is correct
5 Correct 1878 ms 86688 KB Output is correct
6 Correct 3849 ms 94328 KB Output is correct
7 Correct 4041 ms 94460 KB Output is correct
8 Correct 3955 ms 94412 KB Output is correct
9 Correct 4184 ms 95072 KB Output is correct
10 Correct 4289 ms 90420 KB Output is correct
11 Correct 4249 ms 90420 KB Output is correct
12 Correct 4174 ms 91976 KB Output is correct
13 Correct 4003 ms 90468 KB Output is correct
14 Correct 3955 ms 90360 KB Output is correct
15 Correct 1616 ms 94256 KB Output is correct
16 Correct 4293 ms 96872 KB Output is correct
17 Correct 1253 ms 86392 KB Output is correct
18 Correct 1245 ms 86392 KB Output is correct
19 Correct 1253 ms 86500 KB Output is correct
20 Correct 1268 ms 86516 KB Output is correct
21 Incorrect 1304 ms 86524 KB Output isn't correct
22 Halted 0 ms 0 KB -