Submission #1104114

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1104114	2024-10-22T20:10:48 Z	Kirill22	Jump (BOI06_jump)	C++17	100 / 100	5 ms	2384 KB

jump

#include "bits/stdc++.h"
 
using namespace std;
 
struct Int {
    vector<int> a;
 
    Int(int x = 0) : a(1, x) {}
 
    Int& operator+=(const Int& Other) {
        if (a.size() < Other.a.size()) {
            a.resize(Other.a.size());
        }
        int rem = 0;
        for (int i = 0; i < (int) a.size() || rem; i++) {
            if ((int) a.size() == i) {
                a.push_back(0);
            }
            rem += a[i];
            if (i < (int) Other.a.size()) {
                rem += Other.a[i];
            }
            a[i] = rem % 10;
            rem /= 10;
        }
        return *this;
    }
 
    void print() {
        if (a.empty() || (int) a.size() == 1 && a[0] == 0) {
            cout << 0 << '\n';
        } else {
            std::reverse(a.begin(), a.end());
            for (auto& c : a) {
                cout << c;
            }
        }
    }
};
 
const int N = 100 + 22;
Int dp[N][N];
int a[N][N];
 
void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    dp[0][0] = Int(1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int i2 = 0; i2 < i; i2++) {
                if (a[i2][j] == i - i2) {
                    dp[i][j] += dp[i2][j];
                }
            }
            for (int j2 = 0; j2 < j; j2++) {
                if (a[i][j2] == j - j2) {
                    dp[i][j] += dp[i][j2];
                }
            }
        }
    }
    dp[n - 1][n - 1].print();
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Compilation message

jump.cpp: In member function 'void Int::print()':
jump.cpp:30:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   30 |         if (a.empty() || (int) a.size() == 1 && a[0] == 0) {
      |                          ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1104 KB	Output is correct
2	Correct	1 ms	1104 KB	Output is correct
3	Correct	2 ms	1104 KB	Output is correct
4	Correct	1 ms	1104 KB	Output is correct
5	Correct	1 ms	1104 KB	Output is correct
6	Correct	2 ms	1104 KB	Output is correct
7	Correct	1 ms	1104 KB	Output is correct
8	Correct	2 ms	1104 KB	Output is correct
9	Correct	2 ms	1104 KB	Output is correct
10	Correct	2 ms	1104 KB	Output is correct
11	Correct	2 ms	1104 KB	Output is correct
12	Correct	2 ms	1288 KB	Output is correct
13	Correct	2 ms	1104 KB	Output is correct
14	Correct	2 ms	1356 KB	Output is correct
15	Correct	2 ms	1360 KB	Output is correct
16	Correct	4 ms	1872 KB	Output is correct
17	Correct	3 ms	1616 KB	Output is correct
18	Correct	4 ms	1992 KB	Output is correct
19	Correct	4 ms	1616 KB	Output is correct
20	Correct	5 ms	2384 KB	Output is correct