oj.uz

Submission #864387

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

int n;
int m;
string ans;
vector<vector<char>> board;

bool possible(string curr, string ans)
{

    for (int i=0; i<curr.size(); i++)
        if (curr[i]<ans[i]) return true;
        else if (curr[i]>ans[i]) return false;
        
    return true;
}


void bt(int i, int j, string cur){
    if(i==n-1 and j==m-1){
        ans = min(ans, cur);
        return;
    }
    if(i==n-1){
        j++;
        cur+=board[i][j];
        if(possible(cur,ans)){
            bt(i,j,cur);
        }
        return;
    }
    else if(j==m-1){
        i++;
        cur+=board[i][j];
        if(possible(cur,ans)){
            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(possible(cur,ans)){
                bt(i,j,cur);
            }
            return;
        }
        else{
            cur += board[i+1][j];
            if(possible(cur,ans)){
                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];
        }
    }

    for(int i=0; i<n+m-1; i++)
        ans += "{";
    
    string c;
    c += board[0][0];
    
    bt(0,0,c);
    
    cout << ans << endl;
    
    return 0;
}

Compilation message

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

Subtask #1
55.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 9 ms 1884 KB Output is correct
7 Correct 63 ms 7684 KB Output is correct
8 Correct 146 ms 21044 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 147 ms 860 KB Output is correct
11 Correct 332 ms 2020 KB Output is correct
12 Execution timed out 1058 ms 2916 KB Time limit exceeded
13 Execution timed out 1070 ms 5800 KB Time limit exceeded
14 Execution timed out 1046 ms 21692 KB Time limit exceeded
15 Execution timed out 1070 ms 348 KB Time limit exceeded
16 Execution timed out 1096 ms 9192 KB Time limit exceeded