oj.uz

Submission #783398

# Submission time Handle Problem Language Result Execution time Memory
783398 2023-07-14T22:23:02 Z tolbi Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 42000 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 = 1e15;
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 = 5000;
const int MAXSEG = 1;
const int BL = 1;
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;
			}
		}
		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 16091 ms 12200 KB Output is correct
2 Correct 16268 ms 12228 KB Output is correct
3 Correct 16165 ms 15000 KB Output is correct
4 Correct 16431 ms 12244 KB Output is correct
5 Correct 16341 ms 12232 KB Output is correct
6 Correct 5 ms 8276 KB Output is correct
7 Correct 4 ms 8276 KB Output is correct
8 Correct 3 ms 8276 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 3 ms 8276 KB Output is correct
3 Correct 4 ms 8276 KB Output is correct
4 Correct 4 ms 8276 KB Output is correct
5 Correct 4 ms 8276 KB Output is correct
6 Correct 4 ms 8276 KB Output is correct
7 Correct 4 ms 8276 KB Output is correct
8 Correct 4 ms 8284 KB Output is correct
9 Correct 4 ms 8276 KB Output is correct
10 Correct 4 ms 8276 KB Output is correct
11 Correct 56 ms 9268 KB Output is correct
12 Correct 4 ms 8276 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 8584 KB Output is correct
2 Correct 492 ms 8560 KB Output is correct
3 Correct 666 ms 8572 KB Output is correct
4 Correct 703 ms 8576 KB Output is correct
5 Correct 677 ms 8564 KB Output is correct
6 Correct 5 ms 8276 KB Output is correct
7 Correct 4 ms 8276 KB Output is correct
8 Correct 4 ms 8276 KB Output is correct
9 Correct 2731 ms 8572 KB Output is correct
10 Correct 4 ms 8276 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16315 ms 16108 KB Output is correct
2 Correct 16350 ms 16168 KB Output is correct
3 Correct 16145 ms 16184 KB Output is correct
4 Correct 16225 ms 17560 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 8560 KB Output is correct
2 Correct 501 ms 8572 KB Output is correct
3 Correct 649 ms 8576 KB Output is correct
4 Correct 652 ms 8580 KB Output is correct
5 Correct 665 ms 8560 KB Output is correct
6 Correct 16203 ms 16112 KB Output is correct
7 Correct 16129 ms 16168 KB Output is correct
8 Correct 16050 ms 16188 KB Output is correct
9 Correct 16106 ms 17440 KB Output is correct
10 Correct 16461 ms 12224 KB Output is correct
11 Correct 16475 ms 12244 KB Output is correct
12 Correct 16631 ms 15000 KB Output is correct
13 Correct 16139 ms 12244 KB Output is correct
14 Correct 16035 ms 12228 KB Output is correct
15 Correct 8 ms 8276 KB Output is correct
16 Correct 4 ms 8276 KB Output is correct
17 Correct 5 ms 8276 KB Output is correct
18 Correct 5 ms 8276 KB Output is correct
19 Correct 5 ms 8276 KB Output is correct
20 Correct 4 ms 8276 KB Output is correct
21 Correct 4 ms 8256 KB Output is correct
22 Correct 4 ms 8276 KB Output is correct
23 Correct 4 ms 8276 KB Output is correct
24 Correct 4 ms 8256 KB Output is correct
25 Correct 71 ms 10700 KB Output is correct
26 Correct 5 ms 8276 KB Output is correct
27 Correct 2730 ms 8640 KB Output is correct
28 Execution timed out 20062 ms 19956 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 8556 KB Output is correct
2 Correct 477 ms 8560 KB Output is correct
3 Correct 671 ms 8568 KB Output is correct
4 Correct 677 ms 8560 KB Output is correct
5 Correct 668 ms 8552 KB Output is correct
6 Correct 16077 ms 16112 KB Output is correct
7 Correct 16020 ms 16172 KB Output is correct
8 Correct 15974 ms 16184 KB Output is correct
9 Correct 15983 ms 17620 KB Output is correct
10 Correct 16024 ms 12224 KB Output is correct
11 Correct 15959 ms 12244 KB Output is correct
12 Correct 16251 ms 14936 KB Output is correct
13 Correct 16045 ms 12360 KB Output is correct
14 Correct 16204 ms 12224 KB Output is correct
15 Runtime error 147 ms 42000 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -