oj.uz

Submission #383567

# Submission time Handle Problem Language Result Execution time Memory
383567 2021-03-30T09:54:40 Z alishahali1382 Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 249392 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=5010, C=100, T=2, SEGSZ=2*MAXN;
typedef array<array<int, C>, C> DATA;
 
int n, m, k, u, v, x, y, t, a, b, ans;
int H[MAXN][C], V[MAXN][C];
int L[SEGSZ], R[SEGSZ], ts;
DATA seg[SEGSZ];
 
inline void _upd(int &x, int y){ if (x>y) x=y;}
void Make(DATA &A, int tl, int tr){
	// O(m^2.len)
	for (int i=0; i<m; i++) for (int j=0; j<m; j++) A[i][j]=inf;
	for (int i=0; i<m; i++) A[i][i]=0;
	for (int x=tl; x<tr; x++){
		for (int i=0; i<m; i++){
			for (int j=1; j<m; j++) _upd(A[i][j], A[i][j-1]+H[x][j-1]);
			for (int j=m-1; j; j--) _upd(A[i][j-1], A[i][j]+H[x][j-1]);
		}
		for (int i=0; i<m; i++) for (int j=0; j<m; j++) A[i][j]+=V[x][j];
	}/*
	for (int i=0; i<m; i++){
		for (int j=1; j<m; j++) _upd(A[i][j], A[i][j-1]+H[tr][j-1]);
		for (int j=m-1; j; j--) _upd(A[i][j-1], A[i][j]+H[tr][j-1]);
	}*/
}
void Merge(DATA &A, DATA &B, DATA &C){
	// O(m^3)
	for (int i=0; i<m; i++) for (int j=0; j<m; j++) C[i][j]=inf;
	for (int i=0; i<m; i++) for (int k=0; k<m; k++) for (int j=0; j<m; j++)
		C[i][j]=min(C[i][j], A[i][k]+B[k][j]);
}
int Build(int tl, int tr){
	int id=++ts;
	if (tr-tl<=T){
		Make(seg[id], tl, tr);
		return id;
	}
	int mid=(tl+tr)>>1;
	L[id]=Build(tl, mid);
	R[id]=Build(mid, tr);
	Merge(seg[L[id]], seg[R[id]], seg[id]);
	return id;
}
void Set(int id, int tl, int tr, int pos){
	if (pos<tl || tr<=pos) return ;
	if (tr-tl<=T){
		Make(seg[id], tl, tr);
		return ;
	}
	int mid=(tl+tr)>>1;
	Set(L[id], tl, mid, pos);
	Set(R[id], mid, tr, pos);
	Merge(seg[L[id]], seg[R[id]], seg[id]);
}
void init(int nn, int mm, int HH[5000][200], int VV[5000][200]) {
	n=nn;
	m=mm;
//	assert(m<=20); // 39 point subtask  sub124
	for (int i=0; i<n; i++) for (int j=0; j+1<m; j++) H[i][j]=HH[i][j];
	for (int i=0; i+1<n; i++) for (int j=0; j<m; j++) V[i][j]=VV[i][j];
	Build(0, n);
}
 
void changeH(int P, int Q, int W) {
    H[P][Q]=W;
    Set(1, 0, n, P);
}
 
void changeV(int P, int Q, int W) {
    V[P][Q]=W;
    Set(1, 0, n, P);
}
 
int escape(int V1, int V2){
	for (int i=1; i<m; i++) _upd(seg[1][V1][i], seg[1][V1][i-1]+H[n-1][i-1]);
	for (int i=m-1; i; i--) _upd(seg[1][V1][i-1], seg[1][V1][i]+H[n-1][i-1]);
	return seg[1][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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30316 KB Output is correct
2 Correct 18 ms 30316 KB Output is correct
3 Correct 96 ms 31980 KB Output is correct
4 Correct 21 ms 30316 KB Output is correct
5 Correct 18 ms 30316 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 90 ms 1644 KB Output is correct
12 Correct 2 ms 640 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 5612 KB Output is correct
2 Correct 790 ms 5752 KB Output is correct
3 Correct 814 ms 5612 KB Output is correct
4 Correct 834 ms 5740 KB Output is correct
5 Correct 777 ms 5740 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 3755 ms 5632 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 38508 KB Output is correct
2 Correct 24 ms 38380 KB Output is correct
3 Correct 24 ms 38508 KB Output is correct
4 Correct 66 ms 39276 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 5740 KB Output is correct
2 Correct 788 ms 5740 KB Output is correct
3 Correct 813 ms 5612 KB Output is correct
4 Correct 852 ms 5740 KB Output is correct
5 Correct 800 ms 5740 KB Output is correct
6 Correct 26 ms 38380 KB Output is correct
7 Correct 30 ms 38372 KB Output is correct
8 Correct 31 ms 38380 KB Output is correct
9 Correct 66 ms 39404 KB Output is correct
10 Correct 18 ms 30316 KB Output is correct
11 Correct 18 ms 30316 KB Output is correct
12 Correct 103 ms 31980 KB Output is correct
13 Correct 19 ms 30316 KB Output is correct
14 Correct 18 ms 30316 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 2 ms 620 KB Output is correct
20 Correct 2 ms 620 KB Output is correct
21 Correct 2 ms 620 KB Output is correct
22 Correct 1 ms 620 KB Output is correct
23 Correct 2 ms 620 KB Output is correct
24 Correct 2 ms 620 KB Output is correct
25 Correct 90 ms 1644 KB Output is correct
26 Correct 2 ms 620 KB Output is correct
27 Correct 3726 ms 5740 KB Output is correct
28 Correct 11176 ms 244432 KB Output is correct
29 Correct 9480 ms 174748 KB Output is correct
30 Correct 9599 ms 174656 KB Output is correct
31 Correct 11099 ms 249392 KB Output is correct
32 Correct 1 ms 364 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 5628 KB Output is correct
2 Correct 816 ms 5740 KB Output is correct
3 Correct 807 ms 5740 KB Output is correct
4 Correct 803 ms 5696 KB Output is correct
5 Correct 846 ms 5740 KB Output is correct
6 Correct 24 ms 38380 KB Output is correct
7 Correct 24 ms 38380 KB Output is correct
8 Correct 25 ms 38508 KB Output is correct
9 Correct 67 ms 39276 KB Output is correct
10 Correct 18 ms 30316 KB Output is correct
11 Correct 18 ms 30316 KB Output is correct
12 Correct 96 ms 31980 KB Output is correct
13 Correct 18 ms 30316 KB Output is correct
14 Correct 18 ms 30316 KB Output is correct
15 Execution timed out 20094 ms 178828 KB Time limit exceeded
16 Halted 0 ms 0 KB -