oj.uz

Submission #864375

# Submission time Handle Problem Language Result Execution time Memory
864375 2023-10-22T16:10:56 Z gutzzy Pohlepko (COCI16_pohlepko) C++14
40 / 80
 1000 ms 21260 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=="{") 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 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 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 1880 KB Output is correct
7 Correct 46 ms 7508 KB Output is correct
8 Correct 133 ms 21076 KB Output is correct
9 Incorrect 3 ms 348 KB Output isn't correct
10 Execution timed out 1096 ms 604 KB Time limit exceeded
11 Execution timed out 1020 ms 2244 KB Time limit exceeded
12 Execution timed out 1039 ms 3040 KB Time limit exceeded
13 Execution timed out 1066 ms 5640 KB Time limit exceeded
14 Execution timed out 1065 ms 21260 KB Time limit exceeded
15 Execution timed out 1057 ms 544 KB Time limit exceeded
16 Execution timed out 1061 ms 8956 KB Time limit exceeded