Submission #180294

#	Time	Username	Problem	Language	Result	Execution time	Memory
180294		awlintqaa	Pohlepko (COCI16_pohlepko)	C++14	80 / 80	255 ms	12108 KiB

pohlepko

#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 (stderr)

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 / 80