oj.uz

Submission #260094

# Submission time Handle Problem Language Result Execution time Memory
260094 2020-08-09T09:39:19 Z SamAnd Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 70292 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 5003, M = 202, INF = 1000000009;

int n, m;
int h[N][N], v[N][N];

int ans[M][M];

int dp[N][M];
void clc()
{
    for (int f = 0; f < m; ++f)
    {
        for (int i = n - 1; i >= 0; --i)
        {
            if (i == n - 1)
            {
                for (int j = 0; j < m; ++j)
                {
                    if (j == f)
                        dp[i][j] = 0;
                    else
                        dp[i][j] = INF;
                }
            }
            else
            {
                for (int j = 0; j < m; ++j)
                {
                    dp[i][j] = dp[i + 1][j] + v[i][j];
                }
            }
            int minu = INF;
            for (int j = 0; j < m; ++j)
            {
                dp[i][j] = min(dp[i][j], minu);
                minu = min(minu, dp[i][j]);
                minu += h[i][j];
            }
            minu = INF;
            for (int j = m - 1; j >= 0; --j)
            {
                dp[i][j] = min(dp[i][j], minu);
                minu = min(minu, dp[i][j]);
                if (j)
                    minu += h[i][j - 1];
            }
        }
        for (int s = 0; s < m; ++s)
        {
            ans[s][f] = dp[0][s];
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
    n = R;
    m = C;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m - 1; ++j)
        {
            h[i][j] = H[i][j];
        }
    }
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            v[i][j] = V[i][j];
        }
    }
    clc();
}

void changeH(int P, int Q, int W)
{
    h[P][Q] = W;
    clc();
}

void changeV(int P, int Q, int W)
{
    v[P][Q] = W;
    clc();
}

int escape(int V1, int V2)
{
    return ans[V1][V2];
}

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

# Verdict Execution time Memory Grader output
1 Correct 69 ms 28544 KB Output is correct
2 Correct 66 ms 28544 KB Output is correct
3 Correct 156 ms 31352 KB Output is correct
4 Correct 69 ms 28544 KB Output is correct
5 Correct 66 ms 28672 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 110 ms 2936 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 1776 KB Output is correct
2 Correct 404 ms 1536 KB Output is correct
3 Correct 842 ms 1784 KB Output is correct
4 Correct 813 ms 1788 KB Output is correct
5 Correct 800 ms 1784 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 2259 ms 1788 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 52600 KB Output is correct
2 Correct 150 ms 52728 KB Output is correct
3 Correct 178 ms 52608 KB Output is correct
4 Correct 225 ms 54008 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 1656 KB Output is correct
2 Correct 410 ms 1656 KB Output is correct
3 Correct 839 ms 1784 KB Output is correct
4 Correct 816 ms 1784 KB Output is correct
5 Correct 801 ms 1664 KB Output is correct
6 Correct 176 ms 52608 KB Output is correct
7 Correct 149 ms 52608 KB Output is correct
8 Correct 178 ms 52608 KB Output is correct
9 Correct 225 ms 54008 KB Output is correct
10 Correct 66 ms 28544 KB Output is correct
11 Correct 65 ms 28544 KB Output is correct
12 Correct 160 ms 31480 KB Output is correct
13 Correct 66 ms 28544 KB Output is correct
14 Correct 65 ms 28544 KB Output is correct
15 Correct 1 ms 372 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 1 ms 512 KB Output is correct
24 Correct 1 ms 512 KB Output is correct
25 Correct 92 ms 3020 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 2235 ms 1784 KB Output is correct
28 Execution timed out 20096 ms 60220 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 1652 KB Output is correct
2 Correct 401 ms 1640 KB Output is correct
3 Correct 831 ms 1784 KB Output is correct
4 Correct 817 ms 1664 KB Output is correct
5 Correct 799 ms 1664 KB Output is correct
6 Correct 179 ms 52600 KB Output is correct
7 Correct 158 ms 52600 KB Output is correct
8 Correct 184 ms 52600 KB Output is correct
9 Correct 224 ms 54008 KB Output is correct
10 Correct 68 ms 28664 KB Output is correct
11 Correct 65 ms 28544 KB Output is correct
12 Correct 156 ms 31352 KB Output is correct
13 Correct 66 ms 28544 KB Output is correct
14 Correct 69 ms 28664 KB Output is correct
15 Correct 5717 ms 70292 KB Output is correct
16 Execution timed out 20076 ms 68344 KB Time limit exceeded
17 Halted 0 ms 0 KB -