Submission #883662

#TimeUsernameProblemLanguageResultExecution timeMemory
883662vjudge1Pohlepko (COCI16_pohlepko)C++17
80 / 80
47 ms4700 KiB
#ifndef Local #pragma GCC optimize("O3,unroll-loops") const int lim=2e5+100; #else const int lim=1e3+100; #endif #include "bits/stdc++.h" using namespace std; #define int long long #define pb push_back const int mod=1e9+7; using pii=pair<int,int>; inline void solve(){ int n,m; cin>>n>>m; string s[n]; for(int i=0;i<n;i++){ cin>>s[i]; } string res={s[0][0]}; set<pii>all{{0,0}},nexty; for(int i=1;i<n+m-1;i++){ char mini=CHAR_MAX; for(pii cor:all){ if(cor.first+1<n){ if(s[cor.first+1][cor.second]==mini){ nexty.insert({cor.first+1,cor.second}); }else if(s[cor.first+1][cor.second]<mini){ nexty.clear(); nexty.insert({cor.first+1,cor.second}); mini=s[cor.first+1][cor.second]; } } if(cor.second+1<m){ if(s[cor.first][cor.second+1]==mini){ nexty.insert({cor.first,cor.second+1}); }else if(s[cor.first][cor.second+1]<mini){ nexty.clear(); nexty.insert({cor.first,cor.second+1}); mini=s[cor.first][cor.second+1]; } } } res.pb(mini); swap(nexty,all); nexty.clear(); } cout<<res<<"\n"; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); #ifdef Local freopen(".in","r",stdin); freopen(".out","w",stdout); #else //freopen("grass.in","r",stdin); //freopen("grass.out","w",stdout); #endif int t=1; //cin>>t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...