oj.uz

Submission #783079

# Submission time Handle Problem Language Result Execution time Memory
783079 2023-07-14T15:05:07 Z tolbi Wombats (IOI13_wombats) C++17
55 / 100
 246 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 = 1e15;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "wombats.h"
vector<vector<vector<ll>>> segtree;
int n, m;
ll v[5000][200],h[5000][200];
int opt[200][200];
void merge(int node){
	if (node*2+1>=segtree.size()){
		int pos = node-segtree.size()/2;
		if (pos>=n){
			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;
				}
			}
			return;
		}
		for (int i = 0; i < m; i++){
			ll crr = 0;
			for (int j = i; j < m; j++){
				segtree[node][i][j]=crr+v[pos][j];
				if (j<m-1) crr+=h[pos][j];
			}
			crr=0;
			for (int j = i; j >= 0; j--){
				segtree[node][i][j]=crr+v[pos][j];
				if (j>0) crr+=h[pos][j-1];
			}
		}
		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 < 5000; i++){
		for (int j = 0; j < 200; 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]=0ll;
		}
	}
	segtree.resize(tol(ceil(log2(n)+1))-1,vector<vector<ll>>(m,vector<ll>(m,0)));
	for (int i = segtree.size()-1; i >= 0; i--){
		merge(i);
	}
}
void changeH(int P, int Q, int W) {
	h[P][Q]=W;
	P+=segtree.size()/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+=segtree.size()/2;
	merge(P);
	while (P>0){
		P=(P-1)/2;
		merge(P);
	}
}
int escape(int V1, int V2) {
	return segtree[0][V1][V2];
	return 23;
}

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: In function 'void merge(int)':
wombats.cpp:36:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  if (node*2+1>=segtree.size()){
      |      ~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21204 KB Output is correct
2 Correct 11 ms 21220 KB Output is correct
3 Correct 66 ms 22816 KB Output is correct
4 Correct 14 ms 21268 KB Output is correct
5 Correct 12 ms 21204 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 8 ms 15956 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15900 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 8 ms 16284 KB Output is correct
5 Correct 8 ms 16204 KB Output is correct
6 Correct 11 ms 16180 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 8 ms 16188 KB Output is correct
9 Correct 8 ms 16196 KB Output is correct
10 Correct 8 ms 16212 KB Output is correct
11 Correct 64 ms 17396 KB Output is correct
12 Correct 8 ms 16212 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 37156 KB Output is correct
2 Correct 55 ms 36708 KB Output is correct
3 Correct 75 ms 37336 KB Output is correct
4 Correct 74 ms 37308 KB Output is correct
5 Correct 71 ms 36724 KB Output is correct
6 Correct 7 ms 15936 KB Output is correct
7 Correct 7 ms 15896 KB Output is correct
8 Correct 8 ms 15940 KB Output is correct
9 Correct 229 ms 37332 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26196 KB Output is correct
2 Correct 14 ms 26172 KB Output is correct
3 Correct 19 ms 26312 KB Output is correct
4 Correct 42 ms 27020 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 37164 KB Output is correct
2 Correct 56 ms 36644 KB Output is correct
3 Correct 72 ms 37320 KB Output is correct
4 Correct 76 ms 37324 KB Output is correct
5 Correct 71 ms 36640 KB Output is correct
6 Correct 15 ms 26196 KB Output is correct
7 Correct 14 ms 26196 KB Output is correct
8 Correct 15 ms 26196 KB Output is correct
9 Correct 43 ms 27252 KB Output is correct
10 Correct 11 ms 21204 KB Output is correct
11 Correct 12 ms 21332 KB Output is correct
12 Correct 75 ms 23124 KB Output is correct
13 Correct 11 ms 21332 KB Output is correct
14 Correct 12 ms 21288 KB Output is correct
15 Correct 8 ms 15960 KB Output is correct
16 Correct 8 ms 15932 KB Output is correct
17 Correct 7 ms 15928 KB Output is correct
18 Correct 8 ms 16212 KB Output is correct
19 Correct 8 ms 16212 KB Output is correct
20 Correct 8 ms 16212 KB Output is correct
21 Correct 8 ms 16212 KB Output is correct
22 Correct 8 ms 16212 KB Output is correct
23 Correct 8 ms 16288 KB Output is correct
24 Correct 8 ms 16152 KB Output is correct
25 Correct 64 ms 17508 KB Output is correct
26 Correct 8 ms 16172 KB Output is correct
27 Correct 181 ms 37220 KB Output is correct
28 Runtime error 179 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 81 ms 37320 KB Output is correct
2 Correct 64 ms 36656 KB Output is correct
3 Correct 87 ms 37324 KB Output is correct
4 Correct 78 ms 37328 KB Output is correct
5 Correct 72 ms 36684 KB Output is correct
6 Correct 15 ms 26232 KB Output is correct
7 Correct 16 ms 26196 KB Output is correct
8 Correct 15 ms 26180 KB Output is correct
9 Correct 49 ms 27284 KB Output is correct
10 Correct 12 ms 21292 KB Output is correct
11 Correct 12 ms 21332 KB Output is correct
12 Correct 66 ms 23240 KB Output is correct
13 Correct 12 ms 21324 KB Output is correct
14 Correct 15 ms 21220 KB Output is correct
15 Runtime error 246 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -