oj.uz

Submission #783062

# Submission time Handle Problem Language Result Execution time Memory
783062 2023-07-14T14:43:02 Z tolbi Wombats (IOI13_wombats) C++17
55 / 100
 3675 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];
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 = 0; i < m; i++){
		for (int j = 0; j < m; j++){
			segtree[node][i][j]=INF;
			for (int k = 0; k < m; k++){
				segtree[node][i][j]=min(segtree[node][i][j],segtree[up][i][k]+segtree[down][k][j]);
			}
		}
	}
}
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:35: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]
   35 |  if (node*2+1>=segtree.size()){
      |      ~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21204 KB Output is correct
2 Correct 11 ms 21220 KB Output is correct
3 Correct 66 ms 24088 KB Output is correct
4 Correct 10 ms 21280 KB Output is correct
5 Correct 12 ms 21240 KB Output is correct
6 Correct 7 ms 15896 KB Output is correct
7 Correct 7 ms 15932 KB Output is correct
8 Correct 7 ms 15904 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15900 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 7 ms 16212 KB Output is correct
5 Correct 8 ms 16212 KB Output is correct
6 Correct 8 ms 16268 KB Output is correct
7 Correct 8 ms 16212 KB Output is correct
8 Correct 7 ms 16212 KB Output is correct
9 Correct 7 ms 16212 KB Output is correct
10 Correct 8 ms 16188 KB Output is correct
11 Correct 63 ms 18552 KB Output is correct
12 Correct 9 ms 16196 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 37244 KB Output is correct
2 Correct 823 ms 36624 KB Output is correct
3 Correct 866 ms 37304 KB Output is correct
4 Correct 863 ms 37244 KB Output is correct
5 Correct 833 ms 36632 KB Output is correct
6 Correct 7 ms 15868 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15936 KB Output is correct
9 Correct 3626 ms 37188 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 13 ms 26312 KB Output is correct
2 Correct 14 ms 26220 KB Output is correct
3 Correct 13 ms 26256 KB Output is correct
4 Correct 43 ms 27648 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 37252 KB Output is correct
2 Correct 858 ms 36620 KB Output is correct
3 Correct 881 ms 37244 KB Output is correct
4 Correct 929 ms 37244 KB Output is correct
5 Correct 813 ms 36640 KB Output is correct
6 Correct 14 ms 26324 KB Output is correct
7 Correct 14 ms 26264 KB Output is correct
8 Correct 14 ms 26280 KB Output is correct
9 Correct 42 ms 27584 KB Output is correct
10 Correct 11 ms 21204 KB Output is correct
11 Correct 13 ms 21236 KB Output is correct
12 Correct 65 ms 24052 KB Output is correct
13 Correct 10 ms 21324 KB Output is correct
14 Correct 10 ms 21332 KB Output is correct
15 Correct 7 ms 15932 KB Output is correct
16 Correct 7 ms 15932 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 8 ms 16212 KB Output is correct
19 Correct 8 ms 16268 KB Output is correct
20 Correct 7 ms 16212 KB Output is correct
21 Correct 8 ms 16152 KB Output is correct
22 Correct 8 ms 16112 KB Output is correct
23 Correct 8 ms 16212 KB Output is correct
24 Correct 7 ms 16204 KB Output is correct
25 Correct 64 ms 18524 KB Output is correct
26 Correct 8 ms 16192 KB Output is correct
27 Correct 3675 ms 37236 KB Output is correct
28 Runtime error 167 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 887 ms 37244 KB Output is correct
2 Correct 814 ms 36624 KB Output is correct
3 Correct 865 ms 37244 KB Output is correct
4 Correct 866 ms 37324 KB Output is correct
5 Correct 815 ms 36632 KB Output is correct
6 Correct 13 ms 26196 KB Output is correct
7 Correct 13 ms 26296 KB Output is correct
8 Correct 14 ms 26312 KB Output is correct
9 Correct 42 ms 27588 KB Output is correct
10 Correct 11 ms 21292 KB Output is correct
11 Correct 10 ms 21256 KB Output is correct
12 Correct 70 ms 23972 KB Output is correct
13 Correct 10 ms 21332 KB Output is correct
14 Correct 10 ms 21204 KB Output is correct
15 Runtime error 225 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -