oj.uz

Submission #783413

# Submission time Handle Problem Language Result Execution time Memory
783413 2023-07-14T22:49:30 Z tolbi Wombats (IOI13_wombats) C++17
100 / 100
 5118 ms 186396 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
template<typename X> ostream& operator<<(ostream& os, vector<X> v){for (auto &it : v) os<<it; return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> v){for (auto &it : v) os<<it; return os;}
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define vint(x) vector<int> x
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((long long)(bi)))
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
typedef long long ll;
const ll INF = 1e9;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "wombats.h"
const int MAXM = 200;
const int MAXN = 5000;
const int MAXSEG = 512;
const int BL = 250;
int bls;
//MEMORY LIMIT 	BL*4*200*200 \
TIME LIMIT 	500*(5000/BL+log2(BL))*200*200
ll segtree[MAXSEG][MAXM][MAXM];
int n, m;
ll v[MAXN][MAXM],h[MAXN][MAXM];
int opt[MAXM][MAXM];
int segsize;
ll cost[MAXM][MAXM];
ll newc[MAXM][MAXM];
void merge(int node){
	if (node*2+1>=segsize){
		int blc = node-segsize/2;
		for (int i = 0; i < m; i++){
			for (int j = 0; j < m; j++){
				if (i==j) segtree[node][i][j]=0;
				else segtree[node][i][j]=INF;
			}
		}
		if (blc>=BL) return;
		for (int pos = bls*blc; pos < bls*blc+bls; pos++){
			for (int i = 0; i < m; i++){
				ll crr = 0;
				for (int j = i; j < m; j++){
					cost[i][j]=crr+v[pos][j];
					if (j<m-1) crr+=h[pos][j];
				}
				crr = 0;
				for (int j = i; j >= 0; j--){
					cost[i][j]=crr+v[pos][j];
					if (j>0) crr+=h[pos][j-1];
				}
			}
			for (int i = m-1; i >= 0; i--){
				for (int j = 0; j < m; j++){
					int lrang = 0;
					if (j>0) lrang = max(lrang, opt[i][j-1]);
					int rrang = m-1;
					if (i<m-1) rrang = min(rrang,opt[i+1][j]);
					newc[i][j]=segtree[node][i][lrang]+cost[lrang][j];
					opt[i][j]=lrang;
					for (int k = lrang; k <= rrang; k++){
						if (segtree[node][i][k]+cost[k][j]<newc[i][j]){
							newc[i][j]=segtree[node][i][k]+cost[k][j];
							opt[i][j]=k;
						}
					}
				}
			}
			swap(segtree[node],newc);
		}
		return;
	}
	int up = node*2+1;
	int down = node*2+2;
	for (int i = m-1; i >= 0; i--){
		for (int j = 0; j < m; j++){
			int lrang=0;
			if (j>0) lrang=max(lrang,opt[i][j-1]);
			int rrang=m-1;
			if (i<m-1) rrang=min(rrang,opt[i+1][j]);
			segtree[node][i][j]=segtree[up][i][lrang]+segtree[down][lrang][j];
			opt[i][j]=lrang;
			for (int k = lrang; k <= rrang; k++){
				if (segtree[up][i][k]+segtree[down][k][j]<segtree[node][i][j]){
					segtree[node][i][j]=segtree[up][i][k]+segtree[down][k][j];
					opt[i][j]=k;
				}
			}
		}
	}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n=R,m=C;
	for (int i = 0; i < MAXN; i++){
		for (int j = 0; j < MAXM; j++){
			if (i<R-1 && j<C) v[i][j]=V[i][j];
			else v[i][j]=0ll;
			if (i<R && j<C-1) h[i][j]=H[i][j];
			else h[i][j]=INF;
		}
	}
	bls=(n+BL-1)/BL;
	segsize=tol(ceil(log2(BL)+1))-1;
	for (int i = segsize-1; i >= 0; i--){
		merge(i);
	}
}
void changeH(int P, int Q, int W) {
	h[P][Q]=W;
	P=(P/bls)+segsize/2;
	merge(P);
	while (P>0){
		P=(P-1)/2;
		merge(P);
	}
}
void changeV(int P, int Q, int W) {
	v[P][Q]=W;
	P=(P/bls)+segsize/2;
	merge(P);
	while (P>0){
		P=(P-1)/2;
		merge(P);
	}
}
int escape(int V1, int V2) {
	return segtree[0][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]
   15 |  int res;
      |      ^~~
wombats.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
wombats.cpp:36:1: warning: multi-line comment [-Wcomment]
   36 | //MEMORY LIMIT  BL*4*200*200 \
      | ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 99688 KB Output is correct
2 Correct 434 ms 99704 KB Output is correct
3 Correct 482 ms 101400 KB Output is correct
4 Correct 466 ms 99636 KB Output is correct
5 Correct 469 ms 99692 KB Output is correct
6 Correct 50 ms 95684 KB Output is correct
7 Correct 50 ms 95668 KB Output is correct
8 Correct 50 ms 95660 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 95684 KB Output is correct
2 Correct 50 ms 95692 KB Output is correct
3 Correct 50 ms 95688 KB Output is correct
4 Correct 54 ms 103592 KB Output is correct
5 Correct 54 ms 103620 KB Output is correct
6 Correct 54 ms 103584 KB Output is correct
7 Correct 53 ms 103628 KB Output is correct
8 Correct 54 ms 103220 KB Output is correct
9 Correct 51 ms 103644 KB Output is correct
10 Correct 66 ms 103244 KB Output is correct
11 Correct 112 ms 104796 KB Output is correct
12 Correct 54 ms 103624 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 136908 KB Output is correct
2 Correct 139 ms 136276 KB Output is correct
3 Correct 158 ms 136688 KB Output is correct
4 Correct 155 ms 136620 KB Output is correct
5 Correct 153 ms 136392 KB Output is correct
6 Correct 49 ms 95692 KB Output is correct
7 Correct 49 ms 95692 KB Output is correct
8 Correct 50 ms 95728 KB Output is correct
9 Correct 341 ms 136656 KB Output is correct
10 Correct 50 ms 96832 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 103972 KB Output is correct
2 Correct 453 ms 103972 KB Output is correct
3 Correct 437 ms 104096 KB Output is correct
4 Correct 471 ms 104692 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 136720 KB Output is correct
2 Correct 137 ms 136232 KB Output is correct
3 Correct 161 ms 136744 KB Output is correct
4 Correct 156 ms 136744 KB Output is correct
5 Correct 149 ms 136328 KB Output is correct
6 Correct 447 ms 103884 KB Output is correct
7 Correct 433 ms 103960 KB Output is correct
8 Correct 470 ms 103944 KB Output is correct
9 Correct 460 ms 104772 KB Output is correct
10 Correct 456 ms 99668 KB Output is correct
11 Correct 456 ms 99668 KB Output is correct
12 Correct 481 ms 101164 KB Output is correct
13 Correct 440 ms 99584 KB Output is correct
14 Correct 438 ms 99668 KB Output is correct
15 Correct 50 ms 95676 KB Output is correct
16 Correct 49 ms 95716 KB Output is correct
17 Correct 48 ms 95696 KB Output is correct
18 Correct 55 ms 103732 KB Output is correct
19 Correct 53 ms 103652 KB Output is correct
20 Correct 71 ms 103548 KB Output is correct
21 Correct 53 ms 103560 KB Output is correct
22 Correct 60 ms 103188 KB Output is correct
23 Correct 52 ms 103584 KB Output is correct
24 Correct 51 ms 103188 KB Output is correct
25 Correct 106 ms 104660 KB Output is correct
26 Correct 51 ms 103628 KB Output is correct
27 Correct 351 ms 136652 KB Output is correct
28 Correct 1483 ms 144852 KB Output is correct
29 Correct 1562 ms 143624 KB Output is correct
30 Correct 1657 ms 143576 KB Output is correct
31 Correct 1547 ms 146048 KB Output is correct
32 Correct 58 ms 96844 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 136652 KB Output is correct
2 Correct 156 ms 136228 KB Output is correct
3 Correct 159 ms 136744 KB Output is correct
4 Correct 179 ms 136744 KB Output is correct
5 Correct 149 ms 136284 KB Output is correct
6 Correct 480 ms 104040 KB Output is correct
7 Correct 431 ms 103972 KB Output is correct
8 Correct 437 ms 104056 KB Output is correct
9 Correct 462 ms 104656 KB Output is correct
10 Correct 442 ms 99592 KB Output is correct
11 Correct 437 ms 99668 KB Output is correct
12 Correct 530 ms 101280 KB Output is correct
13 Correct 440 ms 99676 KB Output is correct
14 Correct 434 ms 99608 KB Output is correct
15 Correct 1415 ms 184724 KB Output is correct
16 Correct 5118 ms 186396 KB Output is correct
17 Correct 51 ms 95652 KB Output is correct
18 Correct 51 ms 95656 KB Output is correct
19 Correct 51 ms 95644 KB Output is correct
20 Correct 53 ms 103584 KB Output is correct
21 Correct 66 ms 103656 KB Output is correct
22 Correct 66 ms 103624 KB Output is correct
23 Correct 54 ms 103600 KB Output is correct
24 Correct 54 ms 103188 KB Output is correct
25 Correct 54 ms 103628 KB Output is correct
26 Correct 53 ms 103260 KB Output is correct
27 Correct 110 ms 104908 KB Output is correct
28 Correct 54 ms 103664 KB Output is correct
29 Correct 345 ms 136712 KB Output is correct
30 Correct 1547 ms 145008 KB Output is correct
31 Correct 4298 ms 185412 KB Output is correct
32 Correct 4244 ms 185656 KB Output is correct
33 Correct 1492 ms 143572 KB Output is correct
34 Correct 4400 ms 184044 KB Output is correct
35 Correct 1523 ms 143468 KB Output is correct
36 Correct 4572 ms 183960 KB Output is correct
37 Correct 1523 ms 145936 KB Output is correct
38 Correct 4478 ms 185964 KB Output is correct
39 Correct 50 ms 96924 KB Output is correct
40 Correct 4643 ms 183964 KB Output is correct