| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 226353 | cgiosy | Wombats (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3")
#pragma GCC target("arch=haswell")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define reset(a) memset(a, 63, sizeof a)
using namespace std;
constexpr int K=20, SZ=504;
int X[5000][200], Y[5000][200];
int T[SZ][200][200], L[SZ], R[SZ], id=1;
int& mini(int& x, int y) { return x=min(x, y); }
void build(int l, int r, int s=0, int e=249, int t=0) {
auto &D=T[t];
reset(D);
if(s==e) {
rep(i, 200) D[i][i]=0;
rep(y, K) {
int i=s*K+y;
rep(j, 200) {
rep(k, 199) mini(D[j][k+1], D[j][k]+X[i][k]);
rep(k, 199) mini(D[j][198-k], D[j][199-k]+X[i][198-k]);
rep(k, 200) D[j][k]+=Y[i][k];
}
}
return;
}
int m=s+e>>1;
if(l<=m) build(l, r, s, m, L[t]=L[t] ?: id++);
if(r>m) build(l, r, m+1, e, R[t]=R[t] ?: id++);
auto &A=T[L[t]], &B=T[R[t]];
rep(a, 200) rep(i, 200) rep(b, 200)
D[a][b]=min(D[a][b], A[a][i]+B[i][b]);
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, M, Q;
cin>>N>>M;
reset(X);
rep(i, N) rep(j, M-1) cin>>X[i][j];
rep(i, N-1) rep(j, M) cin>>Y[i][j];
build(0, 249);
cin>>Q;
while(Q--) {
int t, p, q, w;
cin>>t>>p>>q;
if(t==1) { cin>>w; X[p][q]=w; build(p/K, p/K); }
else if(t==2) { cin>>w; Y[p][q]=w; build(p/K, p/K); }
else cout<<T[0][p][q]<<'\n';
}
}