Submission #243460

#	Time	Username	Problem	Language	Result	Execution time	Memory
243460		N1NT3NDO	Pohlepko (COCI16_pohlepko)	C++14	5 / 80	94 ms	20344 KiB

pohlepko

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back

using namespace std;

short n,m;
string s;
char c[2001][2001];
pair<short,short> dp[2001][2001];

void Rec(short i,short j)
{
  s+=c[i][j];
  if (i==0 && j==0)
    return;
  else Rec(dp[i][j].F,dp[i][j].S);
}

int main()
{
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  for(short i=0;i<n;i++)
    for(short j=0;j<m;j++) cin >> c[i][j];
  dp[0][0]={0,0};
  for(short i=0;i<n;i++)
    for(short j=0;j<m;j++)
          if (i-1>=0 && j-1>=0)
           {
             if (c[i][j]+c[i-1][j]<c[i][j]+c[i][j-1]) dp[i][j]={i-1,j};
             else dp[i][j]={i,j-1};
           }
        else if (i-1>=0 && j-1<0) dp[i][j]={i-1,j};
        else if (i-1<0 && j-1>=0) dp[i][j]={i,j-1};
  s+=c[n-1][m-1];
  Rec(dp[n-1][m-1].F,dp[n-1][m-1].S);
  reverse(s.begin(),s.end());
  cout << s;
}

• Subtask 1: 5 / 80