oj.uz

Submission #783411

# Submission time Handle Problem Language Result Execution time Memory
783411 2023-07-14T22:48:27 Z tolbi Wombats (IOI13_wombats) C++17
55 / 100
 1381 ms 262144 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 = 1024;
const int BL = 500;
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 344 ms 179264 KB Output is correct
2 Correct 342 ms 179096 KB Output is correct
3 Correct 399 ms 180868 KB Output is correct
4 Correct 345 ms 179116 KB Output is correct
5 Correct 343 ms 179184 KB Output is correct
6 Correct 93 ms 175172 KB Output is correct
7 Correct 89 ms 175200 KB Output is correct
8 Correct 88 ms 175160 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 175180 KB Output is correct
2 Correct 89 ms 175216 KB Output is correct
3 Correct 95 ms 175312 KB Output is correct
4 Correct 94 ms 190912 KB Output is correct
5 Correct 94 ms 191024 KB Output is correct
6 Correct 104 ms 191028 KB Output is correct
7 Correct 97 ms 191012 KB Output is correct
8 Correct 96 ms 190160 KB Output is correct
9 Correct 95 ms 190932 KB Output is correct
10 Correct 95 ms 190124 KB Output is correct
11 Correct 147 ms 192348 KB Output is correct
12 Correct 100 ms 190984 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 257044 KB Output is correct
2 Correct 228 ms 256252 KB Output is correct
3 Correct 248 ms 257048 KB Output is correct
4 Correct 259 ms 257048 KB Output is correct
5 Correct 247 ms 256156 KB Output is correct
6 Correct 93 ms 175212 KB Output is correct
7 Correct 93 ms 175180 KB Output is correct
8 Correct 92 ms 175196 KB Output is correct
9 Correct 497 ms 257044 KB Output is correct
10 Correct 93 ms 177584 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 183928 KB Output is correct
2 Correct 349 ms 183840 KB Output is correct
3 Correct 365 ms 183928 KB Output is correct
4 Correct 372 ms 184752 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 257052 KB Output is correct
2 Correct 231 ms 256252 KB Output is correct
3 Correct 253 ms 257016 KB Output is correct
4 Correct 287 ms 257044 KB Output is correct
5 Correct 249 ms 256368 KB Output is correct
6 Correct 345 ms 183928 KB Output is correct
7 Correct 354 ms 183904 KB Output is correct
8 Correct 348 ms 183924 KB Output is correct
9 Correct 373 ms 184708 KB Output is correct
10 Correct 345 ms 179176 KB Output is correct
11 Correct 338 ms 179092 KB Output is correct
12 Correct 393 ms 180852 KB Output is correct
13 Correct 343 ms 179184 KB Output is correct
14 Correct 342 ms 179152 KB Output is correct
15 Correct 92 ms 175160 KB Output is correct
16 Correct 90 ms 175232 KB Output is correct
17 Correct 91 ms 175124 KB Output is correct
18 Correct 102 ms 191088 KB Output is correct
19 Correct 96 ms 190924 KB Output is correct
20 Correct 107 ms 190948 KB Output is correct
21 Correct 96 ms 190976 KB Output is correct
22 Correct 96 ms 190176 KB Output is correct
23 Correct 104 ms 191092 KB Output is correct
24 Correct 107 ms 190192 KB Output is correct
25 Correct 150 ms 192112 KB Output is correct
26 Correct 96 ms 190916 KB Output is correct
27 Correct 467 ms 257048 KB Output is correct
28 Runtime error 559 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 257052 KB Output is correct
2 Correct 225 ms 256140 KB Output is correct
3 Correct 253 ms 256956 KB Output is correct
4 Correct 249 ms 257052 KB Output is correct
5 Correct 237 ms 256204 KB Output is correct
6 Correct 351 ms 183884 KB Output is correct
7 Correct 340 ms 183800 KB Output is correct
8 Correct 358 ms 183996 KB Output is correct
9 Correct 370 ms 184768 KB Output is correct
10 Correct 349 ms 179176 KB Output is correct
11 Correct 341 ms 179188 KB Output is correct
12 Correct 395 ms 180920 KB Output is correct
13 Correct 342 ms 179172 KB Output is correct
14 Correct 348 ms 179228 KB Output is correct
15 Runtime error 1381 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -