oj.uz

Submission #783408

# Submission time Handle Problem Language Result Execution time Memory
783408 2023-07-14T22:45:02 Z tolbi Wombats (IOI13_wombats) C++17
100 / 100
 8535 ms 115344 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 = 256;
const int BL = 100;
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 842 ms 52212 KB Output is correct
2 Correct 838 ms 52212 KB Output is correct
3 Correct 852 ms 53744 KB Output is correct
4 Correct 797 ms 52300 KB Output is correct
5 Correct 835 ms 52300 KB Output is correct
6 Correct 24 ms 48308 KB Output is correct
7 Correct 24 ms 48288 KB Output is correct
8 Correct 25 ms 48252 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 48188 KB Output is correct
2 Correct 24 ms 48296 KB Output is correct
3 Correct 24 ms 48312 KB Output is correct
4 Correct 25 ms 52940 KB Output is correct
5 Correct 25 ms 53024 KB Output is correct
6 Correct 26 ms 52948 KB Output is correct
7 Correct 25 ms 53004 KB Output is correct
8 Correct 25 ms 52796 KB Output is correct
9 Correct 26 ms 53020 KB Output is correct
10 Correct 26 ms 52780 KB Output is correct
11 Correct 78 ms 53964 KB Output is correct
12 Correct 26 ms 52988 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 72832 KB Output is correct
2 Correct 93 ms 72600 KB Output is correct
3 Correct 104 ms 72732 KB Output is correct
4 Correct 104 ms 72744 KB Output is correct
5 Correct 99 ms 72524 KB Output is correct
6 Correct 23 ms 48212 KB Output is correct
7 Correct 24 ms 48272 KB Output is correct
8 Correct 24 ms 48200 KB Output is correct
9 Correct 278 ms 72808 KB Output is correct
10 Correct 25 ms 48980 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 56356 KB Output is correct
2 Correct 786 ms 56312 KB Output is correct
3 Correct 856 ms 56356 KB Output is correct
4 Correct 864 ms 57156 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 72804 KB Output is correct
2 Correct 94 ms 72572 KB Output is correct
3 Correct 106 ms 72792 KB Output is correct
4 Correct 110 ms 72700 KB Output is correct
5 Correct 98 ms 72464 KB Output is correct
6 Correct 805 ms 56360 KB Output is correct
7 Correct 809 ms 56360 KB Output is correct
8 Correct 802 ms 56360 KB Output is correct
9 Correct 817 ms 57036 KB Output is correct
10 Correct 788 ms 52144 KB Output is correct
11 Correct 830 ms 52212 KB Output is correct
12 Correct 834 ms 53748 KB Output is correct
13 Correct 796 ms 52236 KB Output is correct
14 Correct 788 ms 52300 KB Output is correct
15 Correct 25 ms 48208 KB Output is correct
16 Correct 30 ms 48292 KB Output is correct
17 Correct 24 ms 48212 KB Output is correct
18 Correct 30 ms 52980 KB Output is correct
19 Correct 26 ms 53016 KB Output is correct
20 Correct 30 ms 52948 KB Output is correct
21 Correct 33 ms 53000 KB Output is correct
22 Correct 26 ms 52760 KB Output is correct
23 Correct 25 ms 53040 KB Output is correct
24 Correct 26 ms 52684 KB Output is correct
25 Correct 78 ms 54000 KB Output is correct
26 Correct 26 ms 52948 KB Output is correct
27 Correct 313 ms 72736 KB Output is correct
28 Correct 2560 ms 80800 KB Output is correct
29 Correct 2412 ms 79404 KB Output is correct
30 Correct 2427 ms 79308 KB Output is correct
31 Correct 2470 ms 81900 KB Output is correct
32 Correct 24 ms 48948 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 72992 KB Output is correct
2 Correct 86 ms 72460 KB Output is correct
3 Correct 113 ms 72800 KB Output is correct
4 Correct 104 ms 72780 KB Output is correct
5 Correct 99 ms 72448 KB Output is correct
6 Correct 827 ms 56364 KB Output is correct
7 Correct 787 ms 56356 KB Output is correct
8 Correct 826 ms 56360 KB Output is correct
9 Correct 819 ms 57084 KB Output is correct
10 Correct 823 ms 52212 KB Output is correct
11 Correct 792 ms 52208 KB Output is correct
12 Correct 853 ms 53748 KB Output is correct
13 Correct 806 ms 52212 KB Output is correct
14 Correct 790 ms 52216 KB Output is correct
15 Correct 1279 ms 104316 KB Output is correct
16 Correct 8535 ms 115344 KB Output is correct
17 Correct 26 ms 48272 KB Output is correct
18 Correct 25 ms 48300 KB Output is correct
19 Correct 24 ms 48236 KB Output is correct
20 Correct 33 ms 52968 KB Output is correct
21 Correct 25 ms 52972 KB Output is correct
22 Correct 32 ms 53056 KB Output is correct
23 Correct 26 ms 53068 KB Output is correct
24 Correct 25 ms 52688 KB Output is correct
25 Correct 26 ms 53052 KB Output is correct
26 Correct 26 ms 52720 KB Output is correct
27 Correct 79 ms 55396 KB Output is correct
28 Correct 25 ms 53068 KB Output is correct
29 Correct 311 ms 72880 KB Output is correct
30 Correct 2482 ms 84608 KB Output is correct
31 Correct 7218 ms 112824 KB Output is correct
32 Correct 7012 ms 112872 KB Output is correct
33 Correct 2435 ms 82936 KB Output is correct
34 Correct 7156 ms 111020 KB Output is correct
35 Correct 2469 ms 83080 KB Output is correct
36 Correct 7179 ms 110716 KB Output is correct
37 Correct 2543 ms 86284 KB Output is correct
38 Correct 7160 ms 113368 KB Output is correct
39 Correct 24 ms 48972 KB Output is correct
40 Correct 7122 ms 111008 KB Output is correct