| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 29702 | Nikefor | Wombats (IOI13_wombats) | C++98 | 0 ms | 0 KiB |
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>
#define inf 1<<22
#define ii pair<int,int>
using namespace std;
int subtask;
int sum;
int ho, ve;
long dis[402][402];
int dp[3001][2][3001][2];
//vector<ii> adj[10001];
int HG[5000][200];
int VG[5000][200];
int toone(int h, int v) { return (h*ho + v); }
int level(int n) { return n/ve; }
/*int dijkstra(int V1, int V2) {
priority_queue<ii, vector<ii>, greater<ii> > q;
q.push(make_pair(0,toone(ho-1,V2)));
bool visit[10002];
for(int i=0; i<10002;i++) visit[i] = false;
int tar = toone(0,V1);
while(!q.empty()) {
ii ne = q.top();
q.pop();
int v = ne.second;
visit[v] = true;
if(v==tar) return ne.first;
for(int i=0; i<adj[v].size(); i++) {
int go = adj[v][i].second;
if(!visit[go]) q.push( make_pair((ne.first+adj[v][i].first),go) );
}
}
}*/
int f(int sh,int sv,int fh,int fv ) {
if(sh==fh and sv==fv) return 0;
if(sh==fh and sv!=fv) return HG[sh][0];
if(sh>fh) return inf
if(sh>3000 or fh>3000) return min( f(sh+1,sv, fh, fv)+VG[sh][sv], f(sh+1, (sv+1)%2, fh, fv )+HG[sh][0]+VG[sh][(sv+1)%2]);
if(dp[sh][sv][fh][fv]) return dp[sh][sv][fh][fv];
else dp[sh][sv][fh][fv] = min( f(sh+1,sv, fh, fv)+VG[sh][sv], f(sh+1, (sv+1)%2, fh, fv )+HG[sh][0]+VG[sh][(sv+1)%2]);
return dp[sh][sv][fh][fv];
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
ho = R;
ve = C;
for(int i=0; i<5000; i++)
for(int j=0; j<200; j++) {
HG[i][j] = H[i][j];
VG[i][j] = V[i][j];
}
if(C==1) {
subtask=1;
// printf("birinci subtask\n");
for(int i=0; i<R-1; i++) sum+= V[i][0];
}
else if(C==2) subtask = 4;
else if(R<=20 and C<=20) {
subtask = 2;
for(int i=0 ; i<(R*C); i++)
for(int j=0; j<(R*C); j++) dis[i][j] = (i==j)?0:inf;
for(int i=0; i<R; i++)
for(int j=0; j<C-1; j++) dis[toone(i,j)][toone(i, j+1)] = dis[toone(i,j+1)][toone(i,j)] = H[i][j];
for(int i=0; i<R-1; i++)
for(int j=0; j<C; j++) dis[toone(i,j)][toone(i+1,j)] = dis[toone(i+1,j)][toone(i,j)] = V[i][j];
for(int i=0; i<(R*C); i++)
for(int j=0; j<(R*C); j++)
for(int k=0; k<(R*C); k++) if((dis[i][j]+dis[j][k]) < dis[i][k] and level(i)<=level(j) and level(k)>=level(j)) dis[i][k] = dis[i][j]+dis[j][k];
}
/* else {
subtask = 3;
for(int i=0; i<R; i++)
for(int j=0; j<C-1; j++) {
int v1 = toone(i,j), v2=toone(i,j+1);
adj[v1].push_back(make_pair(H[i][j],v2));
adj[v2].push_back(make_pair(H[i][j], v1));
}
for(int i=0; i<R-1; i++)
for(int j=0; j<C; j++) {
int v1= toone(i,j), v2 = toone(i+1,j);
adj[v1].push_back(make_pair(V[i][j], v2));
adj[v2].push_back(make_pair(V[i][j], v1));
}
}*/
}
void changeH(int P, int Q, int W) {
/* if(subtask==3) {
int v1 = toone(P,Q), v2 = toone(P,Q+1);
for(int i=0; i<adj[v1].size();i++) if(adj[v1][i].second==v2) adj[v1][i].first = W;
for(int i=0; i<adj[v2].size();i++) if(adj[v2][i].second==v1) adj[v2][i].first = W;
}*/
HG[P][Q] = W;
}
void changeV(int P, int Q, int W) {
if(subtask==1) {
sum+= (W-VG[P][Q]);
}
/* if(subtask==3) {
int v1 = toone(P,Q), v2 = toone(P+1,Q);
for(int i=0; i<adj[v1].size();i++) if(adj[v1][i].second==v2) adj[v1][i].first = W;
for(int i=0; i<adj[v2].size();i++) if(adj[v2][i].second==v1) adj[v2][i].first = W;
}*/
VG[P][Q] = W;
}
int escape(int V1, int V2) {
if(subtask==1) return sum;
if(subtask==2) return dis[toone(0,V1)][toone(ho-1,V2)];
// if(subtask==3) return dijkstra(V1,V2);
if(subtask==4) return f(0, V1, ho-1, V2);
return 42;
}