oj.uz

Submission #241925

# Submission time Handle Problem Language Result Execution time Memory
241925 2020-06-26T11:03:18 Z Vimmer Jetpack (COCI16_jetpack) C++14
80 / 80
 57 ms 9728 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100501
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9


using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 3> a3;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


pair <int, int> dp[10][N];

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;

    cin >> m;

    n = 10;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) dp[i][j].F = -2;

    dp[n - 1][0] = {0, 0};

    string s[n];

    for (int i = 0; i < n; i++) cin >> s[i];

    for (int j = 0; j < m - 1; j++)
        for (int i = 0; i < n; i++)
        {
            if (dp[i][j].F == -2) continue;

            if (i + 1 != n && s[i + 1][j + 1] == '.') dp[i + 1][j + 1] = {i, j};

            if (i - 1 >= 0 && s[i - 1][j + 1] == '.') dp[i - 1][j + 1] = {i, j};

            if (i == n - 1 && s[i][j + 1] == '.') dp[i][j + 1] = {i, j};

            if (i == 0 && s[i][j + 1] == '.') dp[i][j + 1] = {i, j};
        }

    int x = -1, y = -1;

    for (int i = 0; i < n; i++)
      if (dp[i][m - 1].F != -2) {x = i; y = m - 1;}

    vector <pair <int, int> > gr; gr.clear();

    int koler = 0, tmr = m - 1;

    while (x != n - 1 || y != 0)
    {
        int nx = dp[x][y].F, ny = dp[x][y].S;

        if (nx < x || (nx == x && x == n - 1))
        {
            if (koler != 0) {gr.pb({tmr, koler}); koler = 0;}

            tmr--;

            x = nx; y = ny;

            continue;
        }

        koler++;

        x = nx; y = ny;

        tmr--;
    }

    if (koler != 0) gr.pb({tmr, koler});

    reverse(gr.begin(), gr.end());

    cout << sz(gr) << endl;

    for (auto it : gr) cout << it.F << " " << it.S << endl;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 11 ms 2176 KB Output is correct
8 Correct 19 ms 4736 KB Output is correct
9 Correct 30 ms 7160 KB Output is correct
10 Correct 57 ms 9728 KB Output is correct