oj.uz

답안 #281554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
281554 2020-08-23T07:52:49 Z Kastanda 웜뱃 (IOI13_wombats) C++11
21 / 100
 189 ms 58360 KB 
// M
#include<bits/stdc++.h>
#include "wombats.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 5005, M = 202, MXS = 512, SQ = 20, INF = 1e9 + 9;
int n, m, H[N][M], V[N][M];
int dp[MXS][M][M];
int TMp[M][M], Opt[M][M];
inline void BuildBlock(int l, int r)
{
        memset(TMp, 63, sizeof(TMp));
        for (int st = 0; st < m; st ++)
        {
                TMp[st][st] = 0;
                for (int i = l; i < r; i ++)
                {
                        for (int j = 1; j < m; j ++)
                                TMp[st][j] = min(TMp[st][j], TMp[st][j - 1] + H[i][j - 1]);
                        for (int j = m - 2; j >= 0; j --)
                                TMp[st][j] = min(TMp[st][j], TMp[st][j + 1] + H[i][j]);
                        for (int j = 0; j < m; j ++)
                                TMp[st][j] += V[i][j];
                }
        }
}
inline void Merge(int id, int le, int ri)
{
        for (int sm = 0; sm < m + m; sm ++)
                for (int st = 0; st < m && st <= m; st ++)
                {
                        int fn = sm - st;
                        int l = fn ? Opt[st][fn - 1] : 0;
                        int r = (st < m - 1) ? Opt[st + 1][fn] : (m - 1);
                        int opt = -1, Mn = INF;
                        for (int i = l; i <= r; i ++)
                                if (Mn > dp[le][st][i] + dp[ri][i][fn])
                                        Mn = dp[le][st][i] + dp[ri][i][fn], opt = i;
                        Opt[st][fn] = opt;
                        dp[id][st][fn] = Mn;
                }
}
void BuildSegTree(int id = 1, int l = 0, int r = n)
{
        if (r - l <= SQ)
        {
                BuildBlock(l, r);
                memcpy(dp[id], TMp, sizeof(TMp));
                return ;
        }
        BuildSegTree(lc, l, md);
        BuildSegTree(rc, md, r);
        Merge(id, lc, rc);
}
void init(int _n, int _m, int _H[5000][200], int _V[5000][200])
{
        n = _n; m = _m;
        for (int i = 0; i < n; i ++)
                for (int j = 0; j + 1 < m; j ++)
                        H[i][j] = _H[i][j];
        for (int i = 0; i + 1 < n; i ++)
                for (int j = 0; j < m; j ++)
                        V[i][j] = _V[i][j];

        BuildSegTree();
}
void Update(int i, int id = 1, int l = 0, int r = n)
{
        if (r - l <= SQ)
        {
                BuildBlock(l, r);
                memcpy(dp[id], TMp, sizeof(TMp));
                return ;
        }
        if (i < md)
                Update(i, lc, l, md);
        else
                Update(i, rc, md, r);
        Merge(id, lc, rc);
}
void changeH(int r, int c, int w)
{
        H[r][c] = w;
        Update(r);
}
void changeV(int r, int c, int w)
{
        V[r][c] = w;
        Update(r);
}
int escape(int st, int fn)
{
        return dp[1][st][fn];
}

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 52 ms 50296 KB Output is correct
2 Correct 51 ms 50296 KB Output is correct
3 Correct 147 ms 53112 KB Output is correct
4 Correct 48 ms 50424 KB Output is correct
5 Correct 51 ms 50428 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 672 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 84 ms 1784 KB Output is correct
12 Correct 1 ms 768 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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