oj.uz

답안 #29694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29694 2017-07-20T10:46:39 Z Nikefor 웜뱃 (IOI13_wombats) C++
9 / 100
 20000 ms 34832 KB 
#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[1001][2][1001][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>1000 or fh>1000) 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, (sv+1)%2, fh, fv  )+HG[sh][0]);
    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;
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 34568 KB Output is correct
2 Correct 3 ms 34568 KB Output is correct
3 Correct 79 ms 34568 KB Output is correct
4 Correct 6 ms 34568 KB Output is correct
5 Correct 3 ms 34568 KB Output is correct
6 Correct 3 ms 34568 KB Output is correct
7 Correct 3 ms 34568 KB Output is correct
8 Correct 0 ms 34568 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 34568 KB Output is correct
2 Correct 3 ms 34568 KB Output is correct
3 Correct 3 ms 34568 KB Output is correct
4 Incorrect 63 ms 34568 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 34568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 20000 ms 34832 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 34568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 34568 KB Output isn't correct
2 Halted 0 ms 0 KB -