Форум Всеукраїнської інтернет-олімпіади NetOI

{$APPTYPE CONSOLE}
var
 o,n,i,j,k:longint;
 b:array[1..200,1..200] of longint;
 a:array[1..200] of longint;

 Function min(a,b:longint):longint;
 begin
  If a<b then min:=a else min:=b;
 end;

 Function max(a,b:longint):longint;
 begin
  If a>b then max:=a else max:=b;
 end;

begin
 read(n);
 For i:=1 to n do read(a[i]);
 For i:=1 to n do b[i,i]:=a[i];
 For i:=2 to n do
  For j:=1 to n-i+1 do
  begin
   b[j,j+i-1]:=1000000000;
   For k:=j to j+i-1 do
   begin
    If k=j then o:=a[k]+b[k+1,j+i-1]
    else if k=j+i-1 then o:=a[k]+b[j,k-1]
    else o:=a[k]+max(b[j,k-1],b[k+1,j+i-1]);
    b[j,j+i-1]:=min(b[j,j+i-1],o);
   end;
  end;
  write(b[1,n]);
end.

program Crossing;

uses
  Math;

type
  TPoint = record
    X, Y: Longint;
  end;  
  PArr = ^TArr;
  TArr = record
    L: Longint;
    St, En: array [1..1000] of TPoint;
  end;

var
  LastC, C, I, J, N, K, CurX, CurY, Y1, Y2, YY2, X1, XX1, X2: Longint;
  NapX, NapY, X0, Y0: Shortint;
  A, B: TArr; // A = Gorisontal; B = Vertical;
  Cur: PArr;

begin
  NapX := 1;
  NapY := 0;
  A.L := 0;
  B.L := 0;
  CurX := 0;
  CurY := 0;
  Read(N);
  C := -3;
  for I := 1 to N do
    begin
      LastC := C;
      Read(C);
      case C of
        -1: begin
              X0 := NapX;
              Y0 := NapY;
              NapX := Y0;
              NapY := -X0;
            end;
        -2: begin
              X0 := NapX;
              Y0 := NapY;
              NapX := -Y0;
              NapY := X0;
            end;
        else
            begin
              if NapY = 0
                then Cur := Addr(A)
                else Cur := Addr(B);
              if LastC < 0
                then
                  begin
                    Inc(Cur^.L);
                    Cur^.St[Cur^.L].X := CurX;
                    Cur^.St[Cur^.L].Y := CurY;
                    CurX := CurX + C * NapX;
                    CurY := CurY + C * NapY;
                    Cur^.En[Cur^.L].X := CurX;
                    Cur^.En[Cur^.L].Y := CurY;
                  end
                else
                  begin
                    CurX := CurX + C * NapX;
                    CurY := CurY + C * NapY;
                    Cur^.En[Cur^.L].X := CurX;
                    Cur^.En[Cur^.L].Y := CurY;
                  end;
            end;
      end;
    end;
  K := 0;  
  for I := 1 to A.L do
    for J := 1 to B.L do
      begin
        Y1  := A.St[i].Y;
        X1  := Min(A.St[i].X, A.En[i].X);
        XX1 := Max(A.St[i].X, A.En[i].X);
        X2  := B.St[J].X;
        Y2  := Min(B.St[J].Y, B.En[J].Y);
        YY2 := Max(B.St[J].Y, B.En[J].Y);
        if (X1 < X2) and (X2 < XX1) and (Y2 < Y1) and (Y1 < YY2) then
          Inc(K)
      end;    

  Writeln(K);
end.

program Derivative;

uses
  Math;

const
  Zero = Ord('0');
  Arr: array [False..True, '0'..'9'] of Longint =
       ((0, 1, 8, 27, 64, 125, 216, 343, 512, 729),
        (0, 1, 4,  9, 16,  25,  36,  49,  64,  81));

var
  I, J, K, NNN, P2, D: Longint;
  Par: Boolean;
  P, P1: Int64;
  S: String;
  Z: Char;
  A: array [1..1020] of Longint;

begin
  Read(P, K);

  I := 1;
  while I <= K do
    begin
      P1 := 0;
      Par := False;
      Str(P, S);
      for J := 1 to Length(S) do
        begin
          Z := S[J];
          Inc(P1, Arr[Par, Z]);
          Par := not Par;
        end;
      P := P1;
      if I <= 1020 then
        begin
          A[i] := P;
          for J := 1 to I - 1 do
            if A[J] = P then
              begin
                D := I - J;
                K := I + (K - I) mod D;
                Break;
              end;
        end;
      Inc(I);
    end;
  Writeln(P);
end.

program Krizis;

uses
  Math;

var
  I, J, L, N, K, T, P: Longint;
  A: array [1..100] of Longint;

begin
  Read(L, N);
  for I := 1 to N do Read(A[i]);
  for I := 1 to N - 1 do
    for J := I to N do
      if A[i] > A[J] then
        begin
          T := A[i];
          A[i] := A[J];
          A[J] := T;
        end;

  L := L + L;
  K := 1;
  P := A[1];
  for I := 2 to N do
    if A[i] - P > L then
      begin
        Inc(K);
        P := A[i]; 
      end;

  Writeln(K);
end.

program MoneyBox;

uses
  Math;
  
type
  PArr = ^TArr;
  TArr = array [0..11000] of Longint;

var
  N, M, Step, I, J, NMin: Longint;
  A: array [1..7] of Longint;
  NewB: PArr; // Linker on position in massive Old
  OldA, NewA: PArr; // Lists of current values
  LastOldA, LastNewA: PArr; // Lists of last monet

begin
  New(NewA);
  New(NewB);
  New(LastNewA);
  FillChar(LastNewA^, SizeOf(LastNewA^), 0);
  FillChar(NewA^, SizeOf(NewA^), 0);
  Read(N);

  NewA^[0] := N;
  for I := 1 to N do Read(A[i]);
  for I := 1 to N - 1 do
    for J := I + 1 to N do
      if A[i] > A[J] then
        begin
          M := A[J];
          A[J] := A[i];
          A[i] := M;
        end;
  Read(M);
  if (A[1] = 1) and (A[2] = 100)
    then NMIn := 103
    else NMIn := 55;

  for I := 1 to N do
    begin
      NewA^[i] := A[i];
      LastNewA^[i] := I;
    end;

  for Step := 2 to Min(NMin, M) do
    begin
      OldA := NewA;
      FillChar(NewB^, SizeOf(NewB^), 0);
      LastOldA := LastNewA;
      New(NewA);
      New(LastNewA);
      FillChar(NewA^, SizeOf(NewA^), 0);
      FillChar(LastNewA^, SizeOf(LastNewA^), 0);
      NewA^[0] := 0;
      LastNewA^[0] := 0;
      for I := 1 to OldA^[0] do
        for J := LastOldA^[i] to N do
          begin
            if NewB^[OldA^[i] + A[J]] = 0 then
              begin
                Inc(NewA^[0]);
                NewB^[OldA^[i] + A[J]] := NewA^[0];
                NewA^[NewA^[0]] := OldA^[i] + A[J];
                LastNewA^[NewA^[0]] := J;
              end;
          end;
    end;
  if M > NMin then
    begin
      OldA := NewA;
      FillChar(NewB^, SizeOf(NewB^), 0);
      LastOldA := LastNewA;
      New(NewA);
      New(LastNewA);
      FillChar(NewA^, SizeOf(NewA^), 0);
      FillChar(LastNewA^, SizeOf(LastNewA^), 0);
      NewA^[0] := 0;
      LastNewA^[0] := 0;
      for I := 1 to OldA^[0] do
        for J := LastOldA^[i] to N do
          begin
            if NewB^[OldA^[i] + A[J]] = 0 then
              begin
                Inc(NewA^[0]);
                NewB^[OldA^[i] + A[J]] := NewA^[0];
                NewA^[NewA^[0]] := OldA^[i] + A[J];
                LastNewA^[NewA^[0]] := J;
              end;
          end;
      NewA^[0] := (NewA^[0] - OldA^[0]) * (M - NMin - 1) + NewA^[0];  
    end;
  Writeln(NewA^[0]);
end.

program Wie;

uses
  Math;

var
  I, J, Z, N, K, MinZ: Longint;
  A: array [1..200, 1..200] of Longint;

begin
  Read(N);
  Read(A[1, 1]);
  K := 2;
  for I := K to N do
    begin
      Read(A[1, I]);
      A[K, I] := A[K-1, I-1] + A[K-1, I];
    end;
  Inc(K);  // 3
  for I := K to N do
    A[K, I] := Max(A[K-1, I-1], A[K-1, I]);

  for K := 4 to N do
    begin
      for I := K to N do
        begin
          MinZ := 1000000000;
          for J := 2 to K - 1 do
            begin
              Z := A[1, I-K+J] + Max(A[J-1, I-K+J-1], A[K-J, I]);
              if MinZ > Z then MinZ := Z;
            end;
          A[K, I] := MinZ;  
        end;
    end;

  Writeln(A[N, N]);
end.

type
br=array[1..10000]of integer;
var z,z1,z2:br;
function mergelenZ(a,b:br;len:longint):integer;
var i,j,k:integer;
begin
i:=1;j:=1;k:=0;
while(j<=len)do begin
        if (a[i]<b[j])and(a[i]<>0) then begin
        k:=k+1;
        z2[k]:=a[i];
        i:=i+1;
        end
        else
        if a[i]=b[j] then begin
        k:=k+1;
        z2[k]:=a[i];
        i:=i+1;
        j:=j+1;
        end
        else begin
        k:=k+1;
        z2[k]:=b[j];
        j:=j+1;
        end;
end;
mergelenZ:=k;
end;
var
vidpovid:longint;
aa,null:br;
k,i,m,leng,leng1,p,j,t:longint;
delta:array[0..200]of integer;
begin
for i:=1 to 10000 do begin
aa[i]:=0;null[i]:=0;z[i]:=0;z1[i]:=0;z2[i]:=0;
end;
read(k);
for i:=1 to k do read(z[i]);leng1:=k;
read(m);
for i:=1 to k do
   for j:=k downto i do
      if z[i]>z[j] then begin
         t:=z[i];
         z[i]:=z[j];
         z[j]:=t;
         end;
         z1:=z;
for i:=1 to m-1 do begin
        for j:=1 to k do begin
                for p:=1 to leng1 do begin
                aa[p]:=z[j]+z1[p];
                end;
        leng:=mergelenZ(z2,aa,leng1);
        end;
        z1:=z2;
        z2:=null;
        delta[i]:=leng-leng1;
     leng1:=leng;
     if (i>2) then
        if (delta[i]=delta[i-1])and(delta[i]=delta[i-2])then break;
end;
vidpovid:=leng1+(m-i-1)*delta[i];
writeln(vidpovid);
end.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i,n) for (int i=0; i<(n); ++i)
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define FORE(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); ++it)
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define CLR(x) memset(x,0,sizeof x)
#define xx first
#define yy second
typedef long long int lli;
typedef pair<int, int> P;
typedef vector<int> vi;


using namespace std;
#define MAXN 2007
#define INF 100000000
int n,t[MAXN],dp[MAXN][MAXN]={0},prawog[MAXN]={0},lewog[MAXN]={0};
deque<P> prawo[MAXN],lewo[MAXN];

void dodaj(deque<P>& q,P p){
        while(!q.empty() && q.back().yy >= p.yy) q.pop_back();
        q.PB(p);
}

int nast(deque<P>& q){
        P x=q.front();
        q.pop_front();
        if(q.empty()) return INF;
        P res=q.front();
        q.push_front(x);
        return res.yy;
}

void go(int l,int r){
//        cout << "op " << prawo[l].front().xx << "/" << prawo[l].front().yy << endl;
//        cout << "op " << lewo[r].front().xx << "/" << lewo[r].front().yy << endl;
        while(prawo[l].front().xx + lewo[r].front().xx < r-l){
                if(nast(prawo[l]) < nast(lewo[r])) prawo[l].pop_front();
                else lewo[r].pop_front();
        }
        dp[l][r]=max(prawo[l].front().yy, lewo[r].front().yy);
//        cout << "go " << l << " " << r << " " << dp[l][r] << endl;
        dodaj(prawo[l], P(r-l+1, dp[l][r]+t[r+1]));
        dodaj( lewo[r], P(r-l+1, dp[l][r]+t[l-1]));
}

int main(){
        //in
        scanf("%d",&n);
        FOR(i,1,n) scanf("%d",&t[i]);
        //rozw
        FOR(i,1,n) {
                prawo[i].PB(P(0,t[i]));
                lewo[i].PB(P(0,t[i]));
        }
        REP(d,n) FOR(i,1,n-d) go(i,i+d);
        //out
        printf("%d\n",dp[1][n]);
        return 0;
}