oj.uz

Submission #783407

# Submission time Handle Problem Language Result Execution time Memory
783407 2023-07-14T22:43:52 Z tolbi Wombats (IOI13_wombats) C++17
76 / 100
 1908 ms 73740 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 = 100;
const int MAXN = 5200;
const int MAXSEG = 1000;
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 198 ms 20808 KB Output is correct
2 Correct 199 ms 20912 KB Output is correct
3 Correct 253 ms 22448 KB Output is correct
4 Correct 200 ms 20812 KB Output is correct
5 Correct 198 ms 20876 KB Output is correct
6 Correct 8 ms 16980 KB Output is correct
7 Correct 9 ms 17016 KB Output is correct
8 Correct 9 ms 16952 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16980 KB Output is correct
2 Correct 8 ms 16980 KB Output is correct
3 Correct 9 ms 16976 KB Output is correct
4 Correct 11 ms 19332 KB Output is correct
5 Correct 10 ms 19312 KB Output is correct
6 Correct 10 ms 19408 KB Output is correct
7 Correct 10 ms 19364 KB Output is correct
8 Correct 10 ms 19212 KB Output is correct
9 Correct 10 ms 19284 KB Output is correct
10 Correct 10 ms 19284 KB Output is correct
11 Correct 65 ms 20332 KB Output is correct
12 Correct 10 ms 19412 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 28768 KB Output is correct
2 Correct 67 ms 28760 KB Output is correct
3 Correct 79 ms 28748 KB Output is correct
4 Correct 80 ms 28764 KB Output is correct
5 Correct 78 ms 28760 KB Output is correct
6 Correct 8 ms 17108 KB Output is correct
7 Correct 9 ms 16980 KB Output is correct
8 Correct 9 ms 17016 KB Output is correct
9 Correct 241 ms 28768 KB Output is correct
10 Correct 9 ms 17364 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 24944 KB Output is correct
2 Correct 213 ms 24936 KB Output is correct
3 Correct 205 ms 24944 KB Output is correct
4 Correct 274 ms 25624 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 28676 KB Output is correct
2 Correct 65 ms 28700 KB Output is correct
3 Correct 79 ms 28668 KB Output is correct
4 Correct 85 ms 28768 KB Output is correct
5 Correct 77 ms 28776 KB Output is correct
6 Correct 206 ms 24944 KB Output is correct
7 Correct 204 ms 24944 KB Output is correct
8 Correct 204 ms 24840 KB Output is correct
9 Correct 233 ms 25780 KB Output is correct
10 Correct 200 ms 20912 KB Output is correct
11 Correct 212 ms 20812 KB Output is correct
12 Correct 259 ms 22460 KB Output is correct
13 Correct 198 ms 20836 KB Output is correct
14 Correct 234 ms 20912 KB Output is correct
15 Correct 8 ms 16980 KB Output is correct
16 Correct 9 ms 16980 KB Output is correct
17 Correct 9 ms 16980 KB Output is correct
18 Correct 10 ms 19384 KB Output is correct
19 Correct 11 ms 19412 KB Output is correct
20 Correct 10 ms 19284 KB Output is correct
21 Correct 10 ms 19412 KB Output is correct
22 Correct 10 ms 19284 KB Output is correct
23 Correct 10 ms 19356 KB Output is correct
24 Correct 9 ms 19284 KB Output is correct
25 Correct 66 ms 20292 KB Output is correct
26 Correct 10 ms 19284 KB Output is correct
27 Correct 266 ms 28656 KB Output is correct
28 Correct 1822 ms 36916 KB Output is correct
29 Correct 1872 ms 38892 KB Output is correct
30 Correct 1908 ms 38748 KB Output is correct
31 Correct 1817 ms 42352 KB Output is correct
32 Correct 9 ms 17412 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 28764 KB Output is correct
2 Correct 64 ms 28764 KB Output is correct
3 Correct 102 ms 28684 KB Output is correct
4 Correct 78 ms 28748 KB Output is correct
5 Correct 76 ms 28768 KB Output is correct
6 Correct 246 ms 24940 KB Output is correct
7 Correct 212 ms 24944 KB Output is correct
8 Correct 203 ms 24844 KB Output is correct
9 Correct 229 ms 25716 KB Output is correct
10 Correct 207 ms 20864 KB Output is correct
11 Correct 200 ms 20912 KB Output is correct
12 Correct 252 ms 22448 KB Output is correct
13 Correct 203 ms 20916 KB Output is correct
14 Correct 199 ms 20908 KB Output is correct
15 Runtime error 250 ms 73740 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -