oj.uz

Submission #864389

# Submission time Handle Problem Language Result Execution time Memory
864389 2023-10-22T16:51:36 Z gutzzy Pohlepko (COCI16_pohlepko) C++14
55 / 80
 1000 ms 21492 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));
    set<int> same;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> board[i][j];
            same.insert(board[i][j]);
        }
    }
    
    if(same.size()==1){
        for(int i=0; i<n+m-1; i++)
            ans += board[0][0];
        cout << ans << endl;
        return 0;
    }
    
    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 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 1368 KB Output is correct
6 Correct 14 ms 1708 KB Output is correct
7 Correct 93 ms 7468 KB Output is correct
8 Correct 238 ms 21044 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 154 ms 756 KB Output is correct
11 Correct 369 ms 2028 KB Output is correct
12 Execution timed out 1049 ms 3008 KB Time limit exceeded
13 Execution timed out 1041 ms 5576 KB Time limit exceeded
14 Execution timed out 1035 ms 21492 KB Time limit exceeded
15 Execution timed out 1047 ms 348 KB Time limit exceeded
16 Execution timed out 1068 ms 9124 KB Time limit exceeded