О программировании

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#!/usr/bin/perl

# https://olegmakarenko.ru/2774055.html

use strict;
use warnings;
use locale;
use utf8;
use open qw(:std :utf8);
use 5.010;
use Time::HiRes qw(gettimeofday tv_interval);

my @f;

sub minmax {
  my ($x, $y) = @_;
  my $c = @{$f[$y-1]}[$x-1];
  my ($mind, $maxd, $minr, $maxr);
  ($mind, $maxd) = minmax($x, $y+1) if (!($c =~ s/D//) && $y<@f);
  ($minr, $maxr) = minmax($x+1, $y) if (!($c =~ s/R//) && $x<@f);
  my $min = defined($mind) ? ($mind<($minr//1e9) ? $mind : $minr) : $minr//0;
  my $max = defined($maxd) ? ($maxd>($maxr//-1e9) ? $maxd : $maxr) : $maxr//0;
  return ($min+$c, $max+$c);
}

sub main {
  while(<>) {
    chomp;
    my @l = split /\s+/;
    push(@f, \@l);
  }
  my $start_time = [gettimeofday];
  my ($min, $max) = minmax(1,1);
  printf("min = %d, max = %d\n",$min,$max);
  printf ("Выполнено за %f секунд\n",tv_interval($start_time,[gettimeofday]));
}

$| = 1; &main;

1
2

export cc=30
(for i in $(seq 1 ${cc}); do for j in $(seq 1 ${cc}); do echo -n $(($RANDOM % 100)) " " ; done; echo; done) | sed -re 's/ +/ /g;s/\s+$//' 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#!/usr/bin/perl

# https://olegmakarenko.ru/2774055.html

use strict;
use warnings;
use locale;
use utf8;
use open qw(:std :utf8);
use 5.010;
use Time::HiRes qw(gettimeofday tv_interval);

my @f;
my %pc;

sub minmax {
  my ($x, $y) = @_;
  return @{$pc{$x."-".$y}} if (exists($pc{$x."-".$y}));
  my $c = @{$f[$y-1]}[$x-1];
  my ($mind, $maxd, $minr, $maxr);
  ($mind, $maxd) = minmax($x, $y+1) if (!($c =~ s/D//) && $y<@f);
  ($minr, $maxr) = minmax($x+1, $y) if (!($c =~ s/R//) && $x<@f);
  my $min = defined($mind) ? ($mind<($minr//1e9) ? $mind : $minr) : $minr//0;
  my $max = defined($maxd) ? ($maxd>($maxr//-1e9) ? $maxd : $maxr) : $maxr//0;
  $pc{$x."-".$y} = [$min+$c, $max+$c];
  return ($min+$c, $max+$c);
}

sub main {
  while(<>) {
    chomp;
    my @l = split /\s+/;
    push(@f, \@l);
  }
  my $start_time = [gettimeofday];
  my ($min, $max) = minmax(1,1);
  printf("min = %d, max = %d\n",$min,$max);
  printf ("Выполнено за %f секунд\n",tv_interval($start_time,[gettimeofday]));
}

$| = 1; &main;