oj.uz

Submission #232202

# Submission time Handle Problem Language Result Execution time Memory
232202 2020-05-16T11:05:22 Z errorgorn Wombats (IOI13_wombats) C++14
28 / 100
 4074 ms 32640 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[1005][105][105];

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 6 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 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 92 ms 3320 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 916 ms 9448 KB Output is correct
2 Correct 884 ms 9336 KB Output is correct
3 Correct 917 ms 9336 KB Output is correct
4 Correct 926 ms 9464 KB Output is correct
5 Correct 886 ms 9464 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4074 ms 9464 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 32632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 911 ms 9464 KB Output is correct
2 Correct 892 ms 9428 KB Output is correct
3 Correct 912 ms 9336 KB Output is correct
4 Correct 917 ms 9464 KB Output is correct
5 Correct 885 ms 9592 KB Output is correct
6 Runtime error 35 ms 32632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 913 ms 9432 KB Output is correct
2 Correct 894 ms 9336 KB Output is correct
3 Correct 915 ms 9468 KB Output is correct
4 Correct 915 ms 9464 KB Output is correct
5 Correct 879 ms 9464 KB Output is correct
6 Runtime error 35 ms 32640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -