oj.uz

Submission #232203

# Submission time Handle Problem Language Result Execution time Memory
232203 2020-05-16T11:07:03 Z errorgorn Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 262144 KB 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;

const int INF=1e9;

int r,c;
static int h[5005][205];
static int v[5005][205];

static int data[16400][100][100];

static int pre[205]; //save space ig
void build(int u,int pos){
	for (int x=1;x<c;x++){
		pre[x]=pre[x-1]+h[pos][x-1];
	}
	
	for (int x=0;x<c;x++){
		for (int y=0;y<c;y++){
			data[u][x][y]=pre[max(x,y)]-pre[min(x,y)]+v[pos][y];
		}
	}
}

void merge(int u){
	int l=u<<1,r=u<<1|1;
	
	for (int x=0;x<c;x++){
		for (int y=0;y<c;y++){
			data[u][x][y]=INF;
			for (int z=0;z<c;z++){
				data[u][x][y]=min(data[u][x][y],data[l][x][z]+data[r][z][y]);
			}
		}
	}
}

void init(int u,int s,int e){
	if (s==e){
		build(u,s);
	}
	else{
		int m=s+e>>1;
		init(u<<1,s,m);
		init(u<<1|1,m+1,e);
		
		merge(u);
	}
}

void update(int u,int i,int s,int e){
	if (s==e){
		build(u,s);
	}
	else{
		int m=s+e>>1;
		
		if (i<=m) update(u<<1,i,s,m);
		else update(u<<1|1,i,m+1,e);
		
		merge(u);
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r=R,c=C;
	
    for (int x=0;x<r;x++){
		for (int y=0;y<c-1;y++){
			h[x][y]=H[x][y];
		}
	}
	
	for (int x=0;x<r-1;x++){
		for (int y=0;y<c;y++){
			v[x][y]=V[x][y];
		}
	}
	
	init(1,0,r-1);
}

void changeH(int P, int Q, int W) {
    h[P][Q]=W;
    update(1,P,0,r-1);
}

void changeV(int P, int Q, int W) {
    v[P][Q]=W;
    update(1,P,0,r-1);
}

int escape(int c1, int c2) {
    return data[1][c1][c2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp: In function 'void init(int, int, int)':
wombats.cpp:48:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~
wombats.cpp: In function 'void update(int, int, int, int)':
wombats.cpp:61:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49536 KB Output is correct
2 Correct 29 ms 49528 KB Output is correct
3 Correct 114 ms 52344 KB Output is correct
4 Correct 29 ms 49480 KB Output is correct
5 Correct 28 ms 49536 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 91 ms 2168 KB Output is correct
12 Correct 5 ms 896 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 8748 KB Output is correct
2 Correct 894 ms 8568 KB Output is correct
3 Correct 922 ms 8824 KB Output is correct
4 Correct 923 ms 8696 KB Output is correct
5 Correct 884 ms 8568 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4038 ms 8892 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 61568 KB Output is correct
2 Correct 35 ms 61560 KB Output is correct
3 Correct 36 ms 61560 KB Output is correct
4 Correct 77 ms 62968 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 8568 KB Output is correct
2 Correct 894 ms 8600 KB Output is correct
3 Correct 904 ms 8696 KB Output is correct
4 Correct 925 ms 8704 KB Output is correct
5 Correct 918 ms 8704 KB Output is correct
6 Correct 38 ms 61560 KB Output is correct
7 Correct 36 ms 61568 KB Output is correct
8 Correct 37 ms 61540 KB Output is correct
9 Correct 80 ms 63012 KB Output is correct
10 Correct 30 ms 49536 KB Output is correct
11 Correct 29 ms 49536 KB Output is correct
12 Correct 111 ms 52344 KB Output is correct
13 Correct 27 ms 49536 KB Output is correct
14 Correct 28 ms 49528 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 404 KB Output is correct
18 Correct 5 ms 896 KB Output is correct
19 Correct 5 ms 896 KB Output is correct
20 Correct 5 ms 896 KB Output is correct
21 Correct 5 ms 896 KB Output is correct
22 Correct 5 ms 896 KB Output is correct
23 Correct 5 ms 896 KB Output is correct
24 Correct 5 ms 896 KB Output is correct
25 Correct 115 ms 3304 KB Output is correct
26 Correct 5 ms 896 KB Output is correct
27 Correct 4116 ms 8704 KB Output is correct
28 Runtime error 3896 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 8652 KB Output is correct
2 Correct 890 ms 8824 KB Output is correct
3 Correct 903 ms 8696 KB Output is correct
4 Correct 918 ms 8824 KB Output is correct
5 Correct 891 ms 8952 KB Output is correct
6 Correct 36 ms 61576 KB Output is correct
7 Correct 35 ms 61568 KB Output is correct
8 Correct 37 ms 61560 KB Output is correct
9 Correct 78 ms 62968 KB Output is correct
10 Correct 28 ms 49536 KB Output is correct
11 Correct 29 ms 49536 KB Output is correct
12 Correct 109 ms 52344 KB Output is correct
13 Correct 29 ms 49536 KB Output is correct
14 Correct 28 ms 49536 KB Output is correct
15 Execution timed out 20095 ms 200232 KB Time limit exceeded
16 Halted 0 ms 0 KB -