oj.uz

답안 #383551

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
383551 2021-03-30T09:26:05 Z alishahali1382 웜뱃 (IOI13_wombats) C++14
39 / 100
 92 ms 27244 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=20;
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];
DATA seg[MAXN<<2];

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]);
}
void Build(int id, int tl, int tr){
	if (tr-tl==1){
		Make(seg[id], tl, tr);
		return ;
	}
	int mid=(tl+tr)>>1;
	Build(id<<1, tl, mid);
	Build(id<<1 | 1, mid, tr);
	Merge(seg[id<<1], seg[id<<1 | 1], seg[id]);
}
void Set(int id, int tl, int tr, int pos){
	if (tr-tl==1){
		Make(seg[id], tl, tr);
		return ;
	}
	int mid=(tl+tr)>>1;
	if (pos<mid) Set(id<<1, tl, mid, pos);
	else Set(id<<1 | 1, mid, tr, pos);
	Merge(seg[id<<1], seg[id<<1 | 1], 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(1, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 22124 KB Output is correct
2 Correct 16 ms 22124 KB Output is correct
3 Correct 92 ms 23788 KB Output is correct
4 Correct 14 ms 22124 KB Output is correct
5 Correct 15 ms 22252 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

# 결과 실행 시간 메모리 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 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 91 ms 1516 KB Output is correct
12 Correct 2 ms 492 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 748 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 26476 KB Output is correct
2 Correct 19 ms 26476 KB Output is correct
3 Correct 19 ms 26476 KB Output is correct
4 Correct 57 ms 27244 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 748 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 748 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -