oj.uz

Submission #864370

# Submission time Handle Problem Language Result Execution time Memory
864370 2023-10-22T16:06:37 Z gutzzy Pohlepko (COCI16_pohlepko) C++14
40 / 80
 1000 ms 21252 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
int m;
string ans = "{";
vector<vector<char>> board;

void bt(int i, int j, string cur){
    if(i==n-1 and j==m-1){
        if(ans=="Z") ans = cur;
        else ans = min(ans,cur);
        return;
    }
    if(i==n-1){
        j++;
        cur+=board[i][j];
        if(ans.size()<cur.size()){
            ans = cur;
            bt(i,j,cur);
        }
        else{
            if(cur<=ans){
                ans = cur;
                bt(i,j,cur);
            }
        }
        return;
    }
    else if(j==m-1){
        i++;
        cur+=board[i][j];
        if(ans.size()<cur.size() or cur<=ans){
            ans = cur;
            bt(i,j,cur);
        }
        return;
    }
    else{
        if(board[i+1][j]!=board[i][j+1]){
            if(board[i+1][j]<board[i][j+1]) i++;
            else j++;
            cur += board[i][j];
            if(ans.size()<cur.size() or cur<=ans){
                ans = cur;
                bt(i,j,cur);
            }
            return;
        }
        else{
            cur += board[i+1][j];
            if(ans.size()<cur.size() or cur<=ans){
                ans = cur;
                bt(i+1,j,cur);
                bt(i,j+1,cur);
            }
            return;
        }
    }
    
}

int main(){
    cin >> n >> m;
    board = vector<vector<char>>(n,vector<char>(m));
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> board[i][j];
        }
    }
    
    string c;
    c += board[0][0];
    
    bt(0,0,c);
    
    cout << ans << endl;
    
    return 0;
}

Subtask #1
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 8 ms 1712 KB Output is correct
7 Correct 47 ms 7404 KB Output is correct
8 Correct 162 ms 21048 KB Output is correct
9 Incorrect 3 ms 348 KB Output isn't correct
10 Execution timed out 1098 ms 604 KB Time limit exceeded
11 Execution timed out 1020 ms 2196 KB Time limit exceeded
12 Execution timed out 1062 ms 2812 KB Time limit exceeded
13 Execution timed out 1038 ms 5740 KB Time limit exceeded
14 Execution timed out 1052 ms 21252 KB Time limit exceeded
15 Execution timed out 1027 ms 528 KB Time limit exceeded
16 Execution timed out 1061 ms 9268 KB Time limit exceeded