Problem:


Problem C: Differential Pulse Code Modulation

差分パルス符号変調

-->

差分パルス符号変調は主に音声信号を圧縮する際に用いられる圧縮手法の一つである．

音声信号は計算機上では整数列(インパルス列)として扱われる．整数列は入力信号を一定時間間隔で標本化(サンプリング)し，振幅を記録したものである．一般にこの整数列は前後の値が近いという傾向がある．これを利用し，前後の値の差分を符号化し，圧縮率を向上させるのが差分パルス符号変調である．

本問題では差分の値をあらかじめ定められた値の集合から選ぶことを考える．この値の集合をコードブックと呼ぶことにする．復号化後の音声信号
yn は以下の式で定められる．

yn = yn
- 1 + C[kn]

ここで kn はプログラムによって出力される出力系列， C[j]
はコードブックの j 番目の値である．ただし yn
は加算によって0未満の値となった場合は0に，255より大きい値となった場合は255にそれぞれ丸められる．また， y0
の値は128とする．

あなたの仕事は，入力信号とコードブックが与えられたときに，元の入力信号と復号化後の出力信号との差の二乗和が最小となるように出力系列を選んで，そのときの差の二乗和を出力するプログラムを書くことである．

例えば，コードブックとして {4, 2, 1, 0, -1, -2, -4} という値のセットを使って
131, 137 という列を圧縮する場合，
y0 = 128, 
y1 = 128 + 4 = 132, 
y2 = 132 + 4 = 136 という列に圧縮すると
二乗和が (131 - 132)^2 + (137 - 136)^2 = 2 と最小になる．

また，同じくコードブックとして {4, 2, 1, 0, -1, -2, -4} という値のセットを使って
131, 123 という列を圧縮する場合，
y0 = 128, 
y1 = 128 + 1 = 129, 
y2 = 129 - 4 = 125 と，先程の例とは違って
131 により近づく +2 を採用しない方が
(131 - 129) ^ 2 + (123 - 125) ^ 2 = 8
というより小さな二乗和が得られる．

上記 2つの例は sample input の最初の 2例である．

Input

入力は複数のデータセットから構成される．各データセットの形式は次に示すとおりである．

N M

C1

C2

...

CM

x1

x2

...

xN

最初の行は，入力データセットの大きさを規定する． N は圧縮する入力信号の長さ(サンプル数)である． M
はコードブックに含まれる値の個数である． N 及び M は1 ≤ N ≤ 20000，1
≤ M ≤ 16を満たす．

これに続く M 行は，コードブックの記述である． Ci はコードブックに含まれる
i 番目の値を表す． Ci は-255 ≤ Ci
≤ 255を満たす．

これに続く N 行は，入力信号の記述である． xi は入力信号を表す整数列の i
番目の値である． xi は0 ≤ xi ≤ 255を満たす．

データセットの中の入力項目は，すべて整数である．入力の終りは，空白文字1個で区切られた2個のゼロのみからなる行で表される．

Output

入力の各データセットに対して， 元の入力信号と復号化後の出力信号との差の二乗和の最小値を一行で出力せよ．

Sample Input

2 7
4
2
1
0
-1
-2
-4
131
137
2 7
4
2
1
0
-1
-2
-4
131
123
10 7
-4
-2
-1
0
1
2
4
132
134
135
134
132
128
124
122
121
122
5 1
255
0
0
0
0
0
4 1
0
255
0
255
0
0 0

Output for the Sample Input

2
8
0
325125
65026



Sample input:
2 7
4
2
1
0
-1
-2
-4
131
137
2 7
4
2
1
0
-1
-2
-4
131
123
10 7
-4
-2
-1
0
1
2
4
132
134
135
134
132
128
124
122
121
122
5 1
255
0
0
0
0
0
4 1
0
255
0
255
0
0 0


Sample output:
2
8
0
325125
65026

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    M = 256

    def f(m, n):
        cs = [I() for _ in range(m)]
        xs = [I() for _ in range(n)]
        d = [inf] * M
        d[128] = 0
        for i in range(n):
            x = xs[i]
            nd = [inf] * M
            for k in range(M):
                v = d[k]
                for j in range(m):
                    c = cs[j]
                    nk = max(min(k+c,255),0)
                    if nd[nk] > v + pow(x-nk, 2):
                        nd[nk] = v + pow(x-nk, 2)
            d = nd
        return min(d)

    while True:
        n,m = LI()
        if m == 0 and n == 0:
            break
        rr.append(f(m,n))

    return '\n'.join(map(str,rr))




print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    M = 256
    sq = [i**2 for i in range(M)]
    nkss = [[sq[abs(x-nk)] for nk in range(M)] for x in range(M)]
    ML = list(range(M))

    def f(m, n):
        cs = [I() for _ in range(m)]
        xs = [I() for _ in range(n)]
        ml = list(range(m))
        d = [inf] * M
        nd = [inf] * M
        d[128] = 0
        for i in range(n):
            nd = [inf] * M
            nks = nkss[xs[i]]
            for j in ml:
                c = cs[j]
                for k in ML:
                    nk = k+c
                    if nk < 0:
                        nk = 0
                    elif nk > 255:
                        nk = 255
                    if nd[nk] > d[k]:
                        nd[nk] = d[k]
            for nk in ML:
                nd[nk] += nks[nk]
            d = nd
        return min(d)

    while True:
        n,m = LI()
        if m == 0 and n == 0:
            break
        rr.append(f(m,n))

    return '\n'.join(map(str,rr))




print(main())

Submission status: Memory Limit Exceeded

Solution code:
import sys
R = lambda:map(int,raw_input().split())
yNum = 256
MAX_VAL = 10**6
while 1:
    n,m = R()
    if not (n or m): break
    c = []
    x = [128]
    for i in xrange(m):
        c.append(int(raw_input()))
    for i in xrange(n):
        x.append(int(raw_input()))
    sub = [[0 for j in xrange(yNum)] for i in xrange(n+1)]
    for i in xrange(1,n+1):
        for j in xrange(yNum):
            sub[i][j] = (j-x[i])**2
    values = [[MAX_VAL for j in xrange(yNum)] for i in xrange(n+1)]
    values[0][128] = 0
    for i in xrange(n):
        for j in xrange(yNum):
            for k in xrange(m):
                if 0 <= j+c[k] <= 255:
                    values[i+1][j+c[k]] = min(values[i+1][j+c[k]], values[i][j]+sub[i+1][j+c[k]])
                elif 0 > j+c[k]:
                    values[i+1][0] = min(values[i+1][0], values[i][j]+sub[i+1][0])
                else:
                    values[i+1][255] = min(values[i+1][255], values[i][j]+sub[i+1][255])
                #if values[i][j] < 10**5: print values[i][j]
    print min(values[n])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    M = 256
    sq = [i**2 for i in range(M)]
    nkss = [[sq[abs(x-nk)] for nk in range(M)] for x in range(M)]
    ML = list(range(M))

    def f(m, n):
        cs = [I() for _ in range(m)]
        xs = [I() for _ in range(n)]
        ml = list(range(m))
        d = [inf] * M
        nd = [inf] * M
        d[128] = 0
        ckl = list(map(lambda x: (max(min(x[0]+x[1], 255), 0), x[1]), (itertools.product(cs, ML))))
        for i in range(n):
            nd = [inf] * M
            for nk,k in ckl:
                if nd[nk] > d[k]:
                    nd[nk] = d[k]
            d = [nn + kk for nn,kk in zip(nd, nkss[xs[i]])]
        return min(d)

    while True:
        n,m = LI()
        if m == 0 and n == 0:
            break
        rr.append(f(m,n))

    return '\n'.join(map(str,rr))




print(main())

Submission status: Accepted

Solution code:
#先人の方々の知恵を借りて、workの評価式と<(x-x_r)^2>のテーブルを使ってみる
#clst、xlst、tableをタプル化してパフォーマンスを向上
#比較的重いtb1へのアクセスをsetにする


def main():
    inf=float("inf")

    while 1 :
        n,m=map(int,input().split())
        if (n,m)==(0,0) : break
        clst=tuple(int(input()) for _ in range(m))
        xlst=tuple(int(input()) for _ in range(n))

        #tb1=tuple(tuple(255 if i+work>255 else 0 if i+work<0 else i+work for work in clst) for i in range(256))
        tb1=set((max(0,min(255,i+work)),i) for work in clst for i in range(256))
        #ij成分が(i-j)^2に対応する行列
        tb2=tuple(tuple((i-j)**2 for j in range(256)) for i in range(256))

        dp_new=[inf]*256
        dp_new[128]=0
        for val in xlst:
            dp_old=dp_new[:]
            dp_new=[inf]*256
            xlst_tb=tb2[val]
            for j,i in tb1:
                error=dp_old[i]+xlst_tb[j]
                if error<dp_new[j] :
                    dp_new[j]=error
        
        print(min(dp_new))

main()

Submission status: Accepted

Solution code:
# AOJ 2199 - 差分パルス符号変調
# 配るDP
import sys


def main():
    inf = float('inf')
    error_list = tuple(tuple((i - j) ** 2 for i in range(256)) for j in range(256))

    while True:
        N, M = map(int, sys.stdin.readline().strip().split())

        if N == 0:
            break

        C = tuple(int(sys.stdin.readline()) for _ in range(M))

        decode_list = tuple(tuple(255 if j + c > 255 else 0 if j + c < 0 else j + c for c in C) for j in range(256))

        # dp 初期化 ---------------------------------------------------------
        dp1 = [inf] * 256
        dp1[128] = 0

        # dp 計算 ---------------------------------------------------------
        for _ in range(N):
            x = int(sys.stdin.readline())
            error_list_x = error_list[x]
            dp2 = [inf] * 256

            for decode_list_j, dp1_j in zip(decode_list, dp1):
                for x_decode in decode_list_j:

                    new_sum_error = dp1_j + error_list_x[x_decode]

                    if new_sum_error < dp2[x_decode]:
                        dp2[x_decode] = new_sum_error

            dp1 = dp2[:]

        print(min(dp1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import product
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def solve(N, M):
    C = [int(input()) for _ in range(M)]
    X = [int(input()) for _ in range(N)]

    ret = [float('inf')] * 256
    ret[128] = 0
    cor = set((max(min(i + c, 255), 0), i) for c, i in product(C, list(range(256))))
    xt = tuple(tuple((x - t)**2 for x in range(256)) for t in range(256))
    for x in X:
        tmp = [float('inf')] * 256
        xt_now = xt[x]
        for t, i in cor:
            v = ret[i]
            if v + xt_now[t] < tmp[t]:
                tmp[t] = v + xt_now[t]
        ret = tmp[:]

    return min(ret)


def main():
    ans = []
    while True:
        N, M = inpl()
        if N == M == 0:
            break
        ans.append(solve(N, M))
    for a in ans:
        print(a)
    return

main()

Submission status: Accepted

Solution code:
# import copy
# answers = []

from sys import stdin
input = stdin
def solve():
    while True:
        n, m = map(int,input.readline().split())
        if n == 0 and m == 0:
            break
        # c = []
        # x = [128]
        INF = float('inf')
        # for i in range(m):
        #     c.append(int(input()))
        c = tuple(int(input.readline()) for i in range(m))
        tb1 = tuple(tuple((i-j)**2 for i in range(256)) for j in range(256))
        tb2 = tuple(tuple(255 if i+ci>255 else 0 if i+ci<0 else i+ci for ci in c) for i in range(256))
        # for j in range(n):
        #     x.append(int(input()))
        # dp = [[INF]*(256) for _ in range(n+1)] #dp[i][j]は信号の大きさj入力した時のi番目の信号との二乗誤差の合計
        dp1 = [INF]*256
        dp2 = [INF]*256
        # prev = set([128])
        # dp[0][128] = 0
        dp1[128] = 0
        for i in range(n):
            x = int(input.readline())
            # nexts = set([])
            # print(prev)
            tb1_x = tb1[x]
            # for j in range(256):
            for j,precost in enumerate(dp1):
                for a in tb2[j]:
                    # a = j + c[k]
                    # a = tb2[j][k]
                    # nexts.add(a)
                    # print(dp2[a],dp1[j] + tb1[a][x])
                    # dp[i+1][a] = min(dp[i+1][a],dp[i][j] + tb1[a][x])
                    newcost = precost+tb1_x[a]
                    if newcost<dp2[a]:
                        dp2[a] = newcost
                    # dp2[a] = min(dp2[a], dp1[j] + tb1_x[a] )
            # prev = nexts
            dp1 = dp2[:]
            dp2 = [INF]*256
        # for i in range(n+1):
        #     print(x[i],"→",*dp[i][120:256])
        print(min(dp1))
solve()
# for ans in answers:
#     print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = lambda: sys.stdin.readline().rstrip() 
    INF = 10**12

    sq_diff = tuple(tuple((i-j)**2 for j in range(256)) for i in range(256))
    while True:
        N, M = map(int, input().split())
        C = tuple(int(input()) for _ in range(M))
        x = tuple(int(input()) for _ in range(N))
        if N==M==0:
            break
        else:
            normalize = tuple(tuple(255 if i+c>255 else 0 if i+c<0
                    else i+c for c in C) for i in range(256))
            dp_cur = [INF]*256
            dp_cur[128] = 0
            dp_next = [INF]*256
            for i in x:
                sq_diff_x = sq_diff[i]
                for j, cost_cur in enumerate(dp_cur):
                    normalize_j = normalize[j]
                    for l in normalize_j:
                        cost_next = cost_cur + sq_diff_x[l]
                        if cost_next < dp_next[l]:
                            dp_next[l] = cost_next

                dp_cur = dp_next[:]
                dp_next = [INF]*256

            print(min(dp_cur))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
from itertools import product
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def solve(N, M):
    C = [int(input()) for _ in range(M)]
    X = [int(input()) for _ in range(N)]

    ret = [float('inf')] * 256
    ret[128] = 0
    cor = set((max(min(i + c, 255), 0), i) for c, i in product(C, list(range(256))))
    xt = tuple(tuple((x - t)**2 for x in range(256)) for t in range(256))
    for x in X:
        tmp = [float('inf')] * 256
        xt_now = xt[x]
        for t, i in cor:
            v = ret[i]
            if v + xt_now[t] < tmp[t]:
                tmp[t] = v + xt_now[t]
        ret = tmp[:]

    return min(ret)


def main():
    ans = []
    while True:
        N, M = inpl()
        if N == M == 0:
            break
        ans.append(solve(N, M))
    for a in ans:
        print(a)
    return


main()

Submission status: Accepted

Solution code:

def solve():
    from sys import stdin
    INF = float('inf')
    input = stdin

    while True:
        N, M = map(int, input.readline().split())
        if N == 0:
            break

        C = tuple(int(input.readline()) for i in range(M))

        # decode table
        tbl_1 = tuple(tuple(255 if i + c > 255 else 0 if i + c < 0
                            else i + c for c in C) for i in range(256))
        # print(tbl_1)
        # tabale of squared difference
        tbl_2 = tuple(tuple((i - j) ** 2 for j in range(256))
                      for i in range(256))
        # print(tbl_2)
        dp1 = [INF] * 256
        dp2 = [INF] * 256
        dp1[128] = 0

        for i in range(N):
            x = int(input.readline())
            tbl_2_x = tbl_2[x]
            for signal, pre_cost in enumerate(dp1):
                for decoded in tbl_1[signal]:
                    new_cost = pre_cost + tbl_2_x[decoded]
                    if new_cost < dp2[decoded]:
                        dp2[decoded] = new_cost
            dp1 = dp2[:]
            dp2 = [INF] * 256
        # print(dp1)
        print(min(dp1))


solve()

Submission status: Accepted

Solution code:
import sys
from itertools import product
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def solve(N, M):
    C = [int(input()) for _ in range(M)]
    X = [int(input()) for _ in range(N)]

    ret = [float('inf')] * 256
    ret[128] = 0
    cor = set((max(min(i + c, 255), 0), i) for c, i in product(C, list(range(256))))
    xt = tuple(tuple((x - t)**2 for x in range(256)) for t in range(256))
    for x in X:
        tmp = [float('inf')] * 256
        xt_now = xt[x]
        for t, i in cor:
            v = ret[i]
            if v + xt_now[t] < tmp[t]:
                tmp[t] = v + xt_now[t]
        ret = tmp[:]

    return min(ret)


def main():
    ans = []
    while True:
        N, M = inpl()
        if N == M == 0:
            break
        ans.append(solve(N, M))
    for a in ans:
        print(a)
    return


main()

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    INF = float('inf')
    f_i = stdin
    
    while True:
        N, M = map(int, f_i.readline().split())
        if N == 0:
            break
        
        C = tuple(int(f_i.readline()) for i in range(M))
        
        # decode table
        tbl_1 = tuple(tuple(255 if i + c > 255 else 0 if i + c < 0 \
                            else i + c for c in C) for i in range(256))
        
        # tabale of squared difference
        tbl_2 = tuple(tuple((i - j) ** 2 for j in range(256)) \
                      for i in range(256))
        
        dp1 = [INF] * 256
        dp2 = [INF] * 256
        dp1[128] = 0
        
        for i in range(N):
            x = int(f_i.readline())
            tbl_2_x = tbl_2[x]
            for signal, pre_cost in enumerate(dp1):
                for decoded in tbl_1[signal]:
                    new_cost = pre_cost + tbl_2_x[decoded]
                    if new_cost < dp2[decoded]:
                        dp2[decoded] = new_cost
            dp1 = dp2[:]
            dp2 = [INF] * 256
        
        print(min(dp1))

solve()

Submission status: Runtime Error

Solution code:
while 1:
	N, M = map(int,raw_input().split(" "))
	if M == N == 0 :
		break
	y0 = 128
	C = [int(raw_input()) for _ in range(M)]
	x = [int(raw_input()) for _ in range(N)]
	dp = {y0:0}
	for i in range(N):
		tmpdp = dict()
		for k,v in dp.iteritems():
			for c in C:
				if k + c > 255:
					y = 255
				elif k + c < 0:
					y = 0
				else :
					y = k + c
				sub_sq = (x[i]-y)**2
				if not(y in tmpdp and v + sub_sq >= tmpdp[y]):
					tmpdp[y] = v + sub_sq
		dp = tmpdp
	print sorted(dp.values())[0]

Submission status: Runtime Error

Solution code:
INF = float("inf")
while 1:
	N, M = map(int,raw_input().split(" "))
	if M == N == 0 :
		break
	y0 = 128
	C = [int(raw_input()) for _ in range(M)]
	x = [int(raw_input()) for _ in range(N)]
	dp = [[INF for _ in range(256)] for _ in range(N+1)]
	dp[0][128] = 0
	for i in range(N):
		for k in range(256):
			v = dp[i][k] 
			if v == INF : continue
			for c in C:
				if k + c > 255: y = 255
				elif k + c < 0: y = 0
				else :          y = k + c
				sub_sq = (x[i]-y)**2
				if  v + sub_sq < dp[i+1][y]: 
					dp[i+1][y] = v + sub_sq
	print sorted(dp[N])[0]

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,m = LI()
        if n == 0 and m == 0:
            break

        cs = [I() for _ in range(m)]
        xs = [I() for _ in range(n)]
        d = collections.defaultdict(int)
        d[128] = 0
        for x in xs:
            n = collections.defaultdict(lambda: inf)
            for k,v in d.items():
                for c in cs:
                    nk = max(min(k+c,255),0)
                    if n[nk] > v + (x-nk) ** 2:
                        n[nk] = v + (x-nk) ** 2
            d = n

        rr.append(min(d.values()))


    return '\n'.join(map(str, rr))


print(main())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

def main():
    N, M = inpl()
    INF = 10**9
    while N:
        C = [int(input()) for _ in range(M)]
        X = [int(input()) for _ in range(N)]
        Y = [[INF]*256 for i in range(N+1)]
    
        for i in range(256):
            Y[0][i] = 0
    
        for i, x in enumerate(X):
            for j in range(256):
                if Y[i][j] == INF:
                    continue
                for c in C:
                    k = min(255, max(0, j+c))
                    Y[i+1][k] = min(Y[i+1][k], Y[i][j] + (x - k)**2)
    
        print(min(Y[-1]))
        N, M = inpl()

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
R = lambda:map(int,raw_input().split())
yNum = 256
MAX_VAL = 10**6
while 1:
    n,m = R()
    if not (n or m): break
    c = []
    x = [128]
    for i in xrange(m):
        c.append(int(raw_input()))
    for i in xrange(n):
        x.append(int(raw_input()))
##    sub = [[0 for j in xrange(yNum)] for i in xrange(n+1)]
##    for i in xrange(1,n+1):
##        for j in xrange(yNum):
##            sub[i][j] = (j-x[i])**2
    values = [[MAX_VAL for j in xrange(yNum)] for i in xrange(n+1)]
    values[0][128] = 0
    for i in xrange(n):
        for j in xrange(yNum):
            for k in xrange(m):
                if 0 <= j+c[k] <= 255:
                    values[i+1][j+c[k]] = min(values[i+1][j+c[k]], values[i][j]+(j+c[k]-x[i+1])**2)
                elif 0 > j+c[k]:
                    values[i+1][0] = min(values[i+1][0], values[i][j]+(0-x[i+1])**2)
                else:
                    values[i+1][255] = min(values[i+1][255], values[i][j]+(255-x[i+1])**2)
                #if values[i][j] < 10**5: print values[i][j]
    print min(values[n])