oj.uz

Submission #634890

# Submission time Handle Problem Language Result Execution time Memory
634890 2022-08-25T08:15:15 Z vendx_greyback Jump (BOI06_jump) C++17
15 / 100
 36 ms 2740 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()

typedef pair<int,int> ppi;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

string add(string num1, string num2){
    
    while(num1.size() < num2.size())
        num1.push_back('0');
        
    while(num1.size() > num2.size())
        num2.push_back('0');
        
    string ans;
    int carry = 0;
    
    for(int i = 0; i < num1.size(); i++){
        int curr = (num1[i] - '0') + (num2[i] - '0') + carry;
        ans.push_back((curr % 10) + '0');
        carry = curr / 10;
    }
    
    if(carry)
        ans.push_back(carry - '0');
        
    return ans;
    
}

int32_t main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin>>n;
	
	int grid[n][n];
	for(int i = 0; i < n; i++)
	    for(int j = 0; j < n; j++)
	        cin>>grid[i][j];
	        
	string dp[n][n];
	
	for(int i = n-1; i >= 0; i--){
	    for(int j = n-1; j >= 0; j--){
	        
	        if(i == n-1 && j == n-1){
	            dp[i][j] = "1";
	            continue;
	        } 
	        
	        
	        dp[i][j] = "0";
	        
	        if(i + grid[i][j] < n)
	            dp[i][j] = add(dp[i][j], dp[i + grid[i][j]][j]);
	            
	        if(j + grid[i][j] < n)
	            dp[i][j] = add(dp[i][j], dp[i][j + grid[i][j]]);
	        
	        
	    }
	}
	
	reverse(all(dp[0][0]));
	cout<<dp[0][0];
	
	return 0;
}

Compilation message

jump.cpp: In function 'std::string add(std::string, std::string)':
jump.cpp:21:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0; i < num1.size(); i++){
      |                    ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 316 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Incorrect 2 ms 340 KB Output isn't correct
15 Incorrect 7 ms 820 KB Output isn't correct
16 Incorrect 19 ms 1600 KB Output isn't correct
17 Incorrect 16 ms 1488 KB Output isn't correct
18 Incorrect 26 ms 2140 KB Output isn't correct
19 Incorrect 23 ms 1948 KB Output isn't correct
20 Incorrect 36 ms 2740 KB Output isn't correct