Submission #383571

#	Time	Username	Problem	Language	Result	Execution time	Memory
383571		alishahali1382	Wombats (IOI13_wombats)	C++14	76 / 100	1448 ms	262148 KiB

wombats

#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=200, T=6, SEGSZ=210*1024*1024/(C*C);
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;
int opt[C][C];
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^2)
	// knuth orz
	for (int i=0; i<m; i++) for (int j=0; j<m; j++) C[i][j]=inf;
	for (int ij=-m; ij<m; ij++){
		for (int i=max(-ij, 0); i<min(m, m-ij); i++){
			int j=i+ij; // 0<=j<m
			int l=(j?opt[i][j-1]:0);
			int r=(i<m-1?opt[i+1][j]:m-1);
			for (int k=l; k<=r; k++){
				int val=A[i][k]+B[k][j];
				if (val<C[i][j]){
					C[i][j]=val;
					opt[i][j]=k;
				}
			}
		}
	}
}
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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24