oj.uz

Submission #180294

# Submission time Handle Problem Language Result Execution time Memory
180294 2020-01-08T16:31:58 Z awlintqaa Pohlepko (COCI16_pohlepko) C++14
80 / 80
 255 ms 12108 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 500
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;//998244353;
const ll inf=1e18*4;
const ld pai=acos(-1);
int n,m;
string s[2009];
set<pi>st;
int check(pi xxx){
        int x=xxx.fi,y=xxx.se;
        return (x>=0 && x<n && y>=0 && y<m);
}
char choose(){
        char z='z'+1;
        for(auto u:st){
                int x=u.fi,y=u.se;
                if(check({x+1,y}))z=min(z,s[x+1][y]);
                if(check({x,y+1}))z=min(z,s[x][y+1]);
        }
        return z;
}
void modify(char z){
        set<pi>ret;
        for(auto u:st){
                int x=u.fi,y=u.se;
                if(check({x+1,y})){
                        if(s[x+1][y]==z){
                                ret.ins({x+1,y});
                        }
                }
                if(check({x,y+1})){
                        if(s[x][y+1]==z){
                                ret.ins({x,y+1});
                        }
                }
        }
        st=ret;
}
int main(){
        cin>>n>>m;
        for(int i=0;i<n;i++)cin>>s[i];
        string ret="";ret+=s[0][0];
        st.ins({0,0});
        int k=n+m-1;
        while(ret.size()<k){
                char x=choose();
                modify(x);
                ret+=x;
        }
        cout<<ret<<endl;
}

Compilation message

pohlepko.cpp: In function 'int main()':
pohlepko.cpp:67:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ret.size()<k){
               ~~~~~~~~~~^~

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 15 ms 504 KB Output is correct
6 Correct 16 ms 1016 KB Output is correct
7 Correct 83 ms 4472 KB Output is correct
8 Correct 255 ms 11896 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 9 ms 760 KB Output is correct
12 Correct 23 ms 1272 KB Output is correct
13 Correct 13 ms 888 KB Output is correct
14 Correct 237 ms 12108 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 183 ms 5004 KB Output is correct