This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 5003;
const int MAXC = 203;
const int INF = 1e9;
constexpr int BLOK = 100;
int H[MAXR][MAXC]={},V[MAXR][MAXC]={};
int dp[(MAXR+BLOK-1)/BLOK*4][MAXC][MAXC];
int opt[MAXC][MAXC];
int cur[MAXC][MAXC];
int C,R,sz;
void merge(int x){
if (x*2+1>=sz){
if (x-sz/2<(R+BLOK-1)/BLOK){
for (int i = 0; i < C; i++){
for (int j = 0; j < C; j++){
dp[x][i][j]=INF;
}
dp[x][i][i]=0;
}
for (int _ = (x-sz/2)*BLOK; _ < min(R,(x-sz/2+1)*BLOK); _++){
for (int i = 0; i < C; i++){
int somma = 0;
for (int j = i; j < C; j++){
cur[i][j]=somma+V[_][j];
somma+=H[_][j];
}
somma = 0;
for (int j = i-1; j >= 0; j--){
somma+=H[_][j];
cur[i][j]=somma+V[_][j];
}
}
int edp[MAXC][MAXC];
for (int i = C-1; i >= 0; i--){
for (int j = 0; j < C; j++){
int lbound = 0;
int rbound = C-1;
if (j) lbound=opt[i][j-1];
if (i+1<C) rbound=opt[i+1][j];
edp[i][j]=dp[x][i][lbound]+cur[lbound][j];
opt[i][j]=lbound;
for (int k = lbound; k <= rbound; k++){
if (dp[x][i][k]+cur[k][j]<edp[i][j]){
edp[i][j]=dp[x][i][k]+cur[k][j];
opt[i][j]=k;
}
}
}
}
for (int i = 0; i < C; i++){
for (int j = 0; j < C; j++){
dp[x][i][j]=edp[i][j];
}
}
}
}
else {
for (int i = 0; i < C; i++){
for (int j = 0; j < C; j++){
if (i==j) dp[x][i][j]=0;
else dp[x][i][j]=INF;
}
}
}
}
else {
for (int i = C-1; i >= 0; i--){
for (int j = 0; j < C; j++){
int lbound = 0;
int rbound = C-1;
if (j) lbound=opt[i][j-1];
if (i+1<C) rbound=opt[i+1][j];
opt[i][j]=lbound;
dp[x][i][j]=dp[x*2+1][i][lbound]+dp[x*2+2][lbound][j];
for (int k = lbound; k <= rbound; k++){
if (dp[x*2+1][i][k]+dp[x*2+2][k][j]<dp[x][i][j]){
dp[x][i][j]=dp[x*2+1][i][k]+dp[x*2+2][k][j];
opt[i][j]=k;
}
}
}
}
}
}
void init(int RR, int CC, int HH[5000][200], int VV[5000][200]) {
C=CC,R=RR;
sz=(1LL<<((int)(ceil(log2((R+BLOK-1)/BLOK)+1))))-1;
for (int i = 0; i < R; i++){
for (int j = 0; j < C; j++){
if (j+1<C) H[i][j]=HH[i][j];
if (i+1<R) V[i][j]=VV[i][j];
}
}
for (int i = sz-1; i >= 0; i--){
merge(i);
}
}
void changeH(int P, int Q, int W) {
H[P][Q]=W;
P/=BLOK;
P+=sz/2;
merge(P);
while (P){
P=(P-1)/2;
merge(P);
}
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
P/=BLOK;
P+=sz/2;
merge(P);
while (P){
P=(P-1)/2;
merge(P);
}
}
int escape(int V1, int V2) {
return dp[0][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;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |