Problem:


Score : 300 points

Problem Statement

In a public bath, there is a shower which emits water for T seconds when the switch is pushed.

If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds.
Note that it does not mean that the shower emits water for T additional seconds.

N people will push the switch while passing by the shower.
The i-th person will push the switch t_i seconds after the first person pushes it.

How long will the shower emit water in total?

Constraints

1 ≤ N ≤ 200,000

1 ≤ T ≤ 10^9

0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≤ 10^9

T and each t_i are integers.

Input

Input is given from Standard Input in the following format:

N T
t_1 t_2 ... t_N

Output

Assume that the shower will emit water for a total of X seconds. Print X.

Sample Input 1

2 4
0 3

Sample Output 1

7

Three seconds after the first person pushes the water, the switch is pushed again and the shower emits water for four more seconds, for a total of seven seconds.

Sample Input 2

2 4
0 5

Sample Output 2

8

One second after the shower stops emission of water triggered by the first person, the switch is pushed again.

Sample Input 3

4 1000000000
0 1000 1000000 1000000000

Sample Output 3

2000000000

Sample Input 4

1 1
0

Sample Output 4

1

Sample Input 5

9 10
0 3 5 7 100 110 200 300 311

Sample Output 5

67



Sample input:
2 4
0 3


Sample output:
7

Submission status: Accepted

Solution code:
N,T = [int(i) for i in input().split()]
ts = [int(i) for i in input().split()]
ret = 0
# for ind in range (1, N):
#     ret += min(T,ts[ind]-ts[ind-1])
for diff in [ts[ind+1]-ts[ind] for ind in range(N-1)]:
    ret += min(T,diff)
print(ret+T)

Submission status: Accepted

Solution code:
N,T = [int(i) for i in input().split()]
ts = [int(i) for i in input().split()]
ret = 0
for ind in range (1, N):
    ret += min(T,ts[ind]-ts[ind-1])
print(ret+T)

Submission status: Accepted

Solution code:
N,T = [int(i) for i in input().split()]
ts = [int(i) for i in input().split()]
ret = 0
ind = 1
while ind < len(ts):
    ret += min(T,ts[ind]-ts[ind-1])
    ind += 1
print(ret+T)

Submission status: Accepted

Solution code:
N, T = map( int, input().split() )
t = list( map( int, input().split() ) )
ans = 0
ptr = 0
while ptr < N:
  nxt = ptr + 1
  while nxt < N and t[ nxt ] <= t[ nxt - 1 ] + T:
    nxt += 1
  ans += t[ nxt - 1 ] + T - t[ ptr ]
  ptr = nxt
print( ans )

Submission status: Accepted

Solution code:
import numpy as np

n, t = map(int, input().split())
ts = np.fromiter(input().split(), dtype=int)
print(sum(np.minimum(np.diff(ts), t)) + t)

Submission status: Accepted

Solution code:
import sys

def solve():
    N, T = map(int, input().split())
    ts = list(map(int, input().split()))

    ans = T
    ans += sum(min(T, ts[i + 1] - ts[i]) for i in range(N - 1))

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,T=map(int,raw_input().split())
t=map(int,raw_input().split())
ans=0
now=0
for i in xrange(n):
    if t[i]<=now:
        ans+=t[i]+T-now
        now=t[i]+T
    else:
        ans+=T
        now=t[i]+T
print ans

Submission status: Accepted

Solution code:
import sys

cin = sys.stdin

N, T = map(int, cin.readline().split())
t = list(map(int, cin.readline().split()))

cnt = 0
for i in range(1,N):
    cnt += min(t[i]-t[i-1], T)
cnt += T
    
print(cnt)

Submission status: Accepted

Solution code:
N, T = list(map(lambda x: int(x), input().split(' ')))
t_list = map(lambda x: int(x), input().split(' '))

summary = 0
time_until = 0
for t in t_list:
    if(time_until <= t):
        summary += T
    else:
        summary += t + T - time_until
    time_until = t + T

print(summary)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
# -*- coding: UTF-8 -*-

n,t=map(int,input().split())
a=[int(i) for i in input().split()]
ans=chk=0
for i in a:
    if chk<=i:
        ans=ans+t
        chk=i+t
    else:
        ans=ans+((i+t)-chk)
        chk=chk+((i+t)-chk)

print(ans)

Submission status: Accepted

Solution code:
from operator import sub
n, t = map(int, input().split())
res = t
temp = list(map(int, input().split()))
for v in map(sub, temp[1:], temp):
  res += min(t, v)
print(res)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
t = list(map(int, input().split()))

ret = T
for i in range(len(t)-1):
    ret += min(t[i+1] - t[i], T)

print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from random import *
from functools import reduce,partial
from time import time

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

def identity(x):
    """Return the input itself."""
    return x

def constant(c):
    """Return an function which always
    returns the input constant c."""
    def const_function(const,*args):
        return const
    return partial(const_function,c)

def inc(c = 1):
    """Return a function which reads an input x and returns x + c as output.
    By default, c equals 1."""
    return lambda x: x + c

def add(*args):
    """Return the sum of the input."""
    def add2(x,y): return x + y
    return reduce(add2,args)

def mapv(f,*lst):
    """Return a vector of the result of map."""
    return list(map(f,*lst))

def vector(*args):
    """Return a vector of input parameters."""
    return args

def sequence(n,f = constant(0)):
    """Return a vector of length n, and initialize the i'th
    item with f(i).By default the vector will initialized with 0."""
    return [f(i) for i in range(0,n)]

def matrix(n,m,f = constant(0)):
    """Return a 2-dim vector which contains n vectors with length m.
    The j's item of vector i will be initialized by f(i,j).By default,
    the vector will be initialized with 0."""
    return [[f(i,j) for j in range(0,m)] for i in range(0,n)]

def flat(v):
    """Return a flat vector which contains the elements of v in their
    origin order.If the input is not a vector, return a vector which
    only contains the input."""
    if not isinstance(v,list): return [v]
    if not v: return []
    return reduce(add,mapv(flat,v))

def partition(v,f = identity):
    """Partition vector v by f(v[i]).
    e.g. partition([1,2,3,1,2,3],identity()) == {1:[1,1,1], 2:[2,2], 3:[3]}
    By default, the vector will be partitioned by identity function."""
    result = {}
    for item in v:
        key = f(item)
        s = result.get(key)
        if s:
            s.append(item)
        else:
            result.update({key:[item]})
    return result

def getValue(key):
    """Return a function which returns the value of key in a hash-map.
    If the key do not exist, it will throw an error."""
    return lambda x: x[key]

def mapValue(f,m):
    """Replace each value in hash-map m with f(value).
    Return the new hash-map."""
    res = {}
    for key in m:
        res.update({key: f(m[key])})
    return res

p = 1000000000 + 7

n,t = readln()
a = readln()
prev = 0
ans = t
for item in a:
    if item > prev + t:
        ans = ans + t
    else:
        ans = ans + item - prev
    prev = item
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
 
 
def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}
 
 
def solve(N, T, t):
    ans = 0
    t_dif = [t[i + 1] - t[i] for i in range(N - 1)]
    
    for i in t_dif:
        if i >= T:
            ans += T
        else:
            ans += i
    
    ans += T
    
    return ans

 
def main():
    N, T = ILI()
    t = ILI()
    print(solve(N, T, t))
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,T=map(int,raw_input().split())
t=map(int,raw_input().split())

sum=0
for i,v in enumerate(t):
	if i==0:pass
	elif (v-t[i-1])>=T:sum+=T
	else:sum+=v-t[i-1]

print sum+T

Submission status: Accepted

Solution code:
def main():
    N, T = map(int, input().split())
    t = tuple(map(int, input().split()))

    i = 0
    x = 0
    while i < N - 1:
        t2 = t[i+1] - t[i]
        if t2 < T:
            x += t2
        else:
            x += T
        i += 1
    print(x + T)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def input_str(row):
    res = []
    for _ in range(row):
        res.append(raw_input().split())
    return res

ipt = input_str(2)
N, T = [int(i) for i in ipt[0]]
t = sorted([int(i) for i in ipt[1]])

total = 0
for i, ti in enumerate(t[:-1]):
    if t[i+1] - t[i] > T:
        total += T
    else:
        total += t[i+1] - t[i]

print total + T

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def solve(n, u, ts):
    res = 0
    end = 0
    for t in ts:
        res += min(u - end + t, u)
        end = u + t
    return res


def main():
    n, u = (int(x) for x in input().split())
    ts = [int(x) for x in input().split()]
    print(solve(n, u, ts))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
t = [int(i) for i in input().split()]
ans = 0
s = 0
d = 0
for t_i in t:
	d = max(t_i + T - s, 0)
	ans += min(d, T)
	s = t_i + T
print(ans)

Submission status: Accepted

Solution code:
n,T=map(int,raw_input().split())
t=map(int,raw_input().split())
i=1
now=T
ans=T
while i<n:
    if t[i]+T<now:
        while t[i]+T<now:
            i+=1
    if t[i]>=now:
        now=t[i]+T
        ans+=T
        i+=1
    elif t[i]+T>=now:
        ans+=t[i]+T-now
        now=t[i]+T
        i+=1
print ans

Submission status: Accepted

Solution code:
#coding: utf-8

N, T = map(int, raw_input().split())
A = map(int, raw_input().split())

total, start, end = 0, 0, 0
for ai in A:
    if ai > end:
        total += end - start
        start = ai
    end = ai + T

if start < end:
    total += end - start

print total

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
ts = list(map(int, input().split()))

ans = 0
tmp_now = ts[0] + T
tmp_start = ts[0]

for i in range(1, N):
    # print(tmp_now, tmp_start)
    if ts[i] <= tmp_now:
        tmp_now = ts[i] + T
    else:
        ans += tmp_now - tmp_start
        tmp_now = ts[i] + T
        tmp_start = ts[i]

ans += tmp_now - tmp_start

print(ans)

Submission status: Accepted

Solution code:
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


def calc(T, t):
        acc = 0
        start = 0
        end = 0
        for i in range(len(t)):
                s = t[i]
                if s >= end:
                        acc += end - start
                        start = s
                end = s + T
        acc += end - start
        print acc

N, T = rdi()
t = rdi()
calc(T, t)

Submission status: Accepted

Solution code:
N,T = list(map(int,input().split()))

Tlist = list(map(int,input().split()))
#######################################

#for t,v in [ map(int,input().split()) for _ in range(N-1) ]:
Tlist.reverse()
goukei = 0
tugi_time = 1e10
for t_i in Tlist:
	goukei += min( T , tugi_time - t_i )
	tugi_time = t_i

print (goukei)

Submission status: Accepted

Solution code:
N,T = map(int, input().split())
t = list(map(int, input().split()))
total = 0 

for i in range(N-1):
    if t[i+1] - t[i] < T:
        total += t[i+1] - t[i]
    else:
        total += T
total += T
print(total)

Submission status: Accepted

Solution code:
n, t = map(int, raw_input().split())
T = map(int, raw_input().split())

rest = 0
ans = 0
prev = 0
for i in xrange(n):
    ti = T[i]
    if rest > 0:
        ans += min(rest, ti - prev)
        rest = max(0, rest - (ti - prev))
    rest = t
    prev = T[i]
print ans + rest

Submission status: Accepted

Solution code:
n, T = [int(_) for _ in raw_input().split()]
s = 0
S = 0
x = 0
for t in [int(_) for _ in raw_input().split()]:
    e = s + T
    if e < t:
        x += e - S
        S = t
    s = t

x += t + T - S

print(x)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())

t = list(map(int, input().split()))

a = 0

for i in range(N-1):
    a += min(T, t[i+1]-t[i])

a += T

print(a)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
ts = list(map(int, input().split()))

ans = sum([min(ts[i + 1] - ts[i], T) for i in range(N - 1)]) + T
print(ans)

Submission status: Accepted

Solution code:
# C
N, T = map(int, input().split())
tv = list(map(int, input().split()))

res = 0

for i in range(len(tv)-1):
    if tv[i+1] - tv[i] < T:
        res += tv[i+1] - tv[i]
    else:
        res += T
res += T

print(res)

Submission status: Accepted

Solution code:
n,T = map(int, input().split(' '))
t = list(map(int, input().split(' ')))

dift = [t[i]-t[i-1] for i in range(1,n)]
ret = [min(dift_,T) for dift_ in dift]

print(sum(ret)+T)

Submission status: Accepted

Solution code:
n, T = map(int, raw_input().split())
t = map(int, raw_input().split())

a = T
for i in xrange(n-1):
    a += min(T, t[i+1] - t[i])
print a

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
mod = 10**9 + 7

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 main():
    n,t = LI()
    a = LI()
    s = 0
    c = 0
    r = 0
    for b in a:
        if c < b:
            r += c - s
            s = b
            c = b+t
        else:
            c = b+t
    r += c-s

    return r


print(main())

Submission status: Accepted

Solution code:
PROBLEM = "A"
FILE = "%s" %(PROBLEM) 
INF = 999999999999999999L
try:
    inFile = open(FILE+".txt")
except:
    inFile = None

def read():
    if inFile:
        return inFile.readline().strip()
    else:
        return raw_input().strip()

def read_ints():
    return map(int,read().split())

n,T = read_ints()
times = read_ints()
ans = 0

for i in xrange(len(times)-1):
    ans += min(T,times[i+1]-times[i])
ans += T
print ans

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
t = [int(x) for x in input().split()]
print(N * T - sum(max(0, T - (t[i+1] - t[i])) for i in range(N - 1)))

Submission status: Accepted

Solution code:
import sys

def solve():
    N, T = map(int, input().split())
    ts = [int(i) for i in input().split()]

    cur = ts[0]
    ans = 0

    for ti in ts[1:]:
        ans += min(T, ti - cur)
        cur = ti

    ans += T

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, T = map(int, raw_input().split())
t = map(int, raw_input().split())
ans = 0

for i in xrange(N-1):
    ans += min(t[i+1] - t[i], T)

ans += T

print ans

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split());
t = [int(x) for x in input().split()];

end = 0;
ans = 0;
for i in range(N) :
    if end > t[i] :
        ans += t[i] + T - end;
        else :
        ans += T;
    end += t[i] + T;
    #print(ans,end);

print(ans);

Submission status: Runtime Error

Solution code:
N,T = map(int, input().split())
prev = 0
ans = 0
for i in range(N):
  t = int(input())
  if prev+T <= t:
    ans += T
  else:
    ans += (t - prev)
    prev = t

print(ans + T)

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
LST = []

for a in A:
  LST.append((a,1))
  LST.append((a+T,-1))
  
LST.sort()

prev = -1
s = 0
ans = 0
for x,y in A:
  if y == 1:
    if s == 0:
      prev = x
    else:
      s += 1
  elif y == -1:
    s -= 1
    if s == 0:
      ans += (x - prev)
  
print(ans)

Submission status: Runtime Error

Solution code:
n,T = map(int,input().split())
t = list(map(int,input().split())
A = [0]*n

for i in range(n):
    if t[i]>T:
        A[i+1] = A[i] + T
    else:
        A[i+1] = A[i]+ t[i]
print(A[n])

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
t = list(map(int, input().split()))

res = 0
for i in range(N - 1):
    res += min(T, t[i + 1] - t[i])

if t[-2] + T <= t[-1]:
    res += T 

print(res)

Submission status: Runtime Error

Solution code:
n, T, *t = map(int, open(0).read().split())
print(sum(min(t[i+1] - t[i], T) for i in range(n)))

Submission status: Runtime Error

Solution code:
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	#print(res)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))

Submission status: Runtime Error

Solution code:
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;

//typedef
//------------------------------------------
using LL = int64_t;
using VL = vector<LL>;
using VVL = vector<VL>;
using VS = vector<string>;
using PLL = pair<LL, LL>;

//container util
//------------------------------------------
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rwhole(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x)
#define EACH(i,c) for(decltype((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) whole(sort, c)
#define RSORT(c) rwhole(sort, c)

//constant
//--------------------------------------------
constexpr double PI  = M_PI;
constexpr int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
// declaretion
template<typename T> istream& operator >>(istream& is, vector<T>& vec);
template<typename T1, typename T2> ostream& operator <<(ostream& os, const pair<T1, T2>& p);
template<typename T> ostream& operator <<(ostream& os, const vector<T>& vec);
template<typename T> ostream& operator <<(ostream& os, const vector<vector<T>>& vv);
template<typename T> vector<T> make_v(size_t a);
template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts);
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v);
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v);

// implementation
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
	for(T& x: vec) is >> x;
	return is;
}
template<typename T1, typename T2>
ostream& operator <<(ostream& os, const pair<T1, T2>& p) {
	os << p.first << "," << p.second;
	return os;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
	for(int i=0; i<vec.size(); i++){
		os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
	}
	return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}

// 多重vector
// auto dp=make_v<int>(4,h,w) みたいに使える
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// 多重vectorのためのfill
// fill_v(dp,0) みたいに使える
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}

template<class T,class U> void chmax(T&a,U b){if(a<b)a=b;}
template<class T,class U> void chmin(T&a,U b){if(b<a)a=b;}
template<typename T> T gcd(T a, T b) { return b?gcd(b,a%b):a;}
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b;}

//main code

int main(int argc, char *argv[])
{
	LL n,T;
	cin >> n >> T;
	VL t(n);
	cin >> t;
	LL ans = T;
	for (int i = 0; i < n-1; i++) {
		if (t[i+1] - t[i] >= T) {
			ans += T;
		} else {
			ans += t[i+1] - t[i];
		}
	}
	cout << ans << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
satooh
N, T = map(int, input().split())
t = list(map(int, input().split()))
ans = 0
for i in range(N - 1):
	if t[i] + T <= t[i + 1]:
		ans += T
	else:
		ans += t[i + 1] - t[i]
ans += T
print(ans)

Submission status: Runtime Error

Solution code:
N,T=map(int,input().split())
s=list(map(int, input().split()))

t=[0,3,5,7,100,110,200,300,311]
ans=0
t_diff=[t[i+1]-t[i] for i in range(N-1)]
print(t_diff)
for i in t_diff:
    if i>T:
        ans+=T
    else:
        ans+=i
# 差分で足し合わせたので最後は計算に入ってない、最後は必ず被らないのでTを加える
print(ans+T)

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
oyu=list(map(int,input.split()))
inl=[]
ans=n*t
for i in range(n-1):
  inl.append(oyu[i+1]-oyu[i])
for i in range(n-1):
  if inl[i]<t:
    ans-=t-inl[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, T = input().split()

f = None
p = None
ans = 0
for t in map(int, input().split())
  if f is None:
    f = t
    p = t - f

  ans += T
  rest = p + T - (t - f)
  if rest > 0:
    ans -= rest

  p = t - f

print(ans)

Submission status: Runtime Error

Solution code:
n,w = list(map(int,input().split()))
lis = []
for i in range(n):
  lis.append(list(map(int,input().split())))

w_id = w - lis[0][0]

for i in range(n):
  lis[i][0] -= lis[0][0]
  
if w_id < 0:
  print(0)
  exit()
  
dp = [[0 for _ in range(w_id+1)] for _ in range(n)]


for i in range(w_id+1):
  if i >= lis[0][0]:
    dp[0][i] = lis[0][1] 

for k in range(1,n):
  for i in range(w_id+1):
    if i < lis[k][0]:
      dp[k][i] = dp[k-1][i]
    else:
      dp[k][i] = max(dp[k-1][i],dp[k-1][i-lis[k][0]]+lis[k][1])
print(dp[n-1][w_id])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

int main(){
    int N, T;
    cin >> N >> T;
    vector<int> t(N);
    for (int i=0; i<N; i++) cin >> t.at(i);

    int ans = T * N;
    for (int i=0; i<N-1; i++){
        ans -= max(0, t.at(i) + T - t.at(i+1));
    }

    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
from collections import*
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    for k,b in d.copy().items():
        if k+w<=W:
            d[k+w]=max(b,d[k]+v)
print(max(d.values()))

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
k=1000000000
for i in map(int,input().split()):
  ans+=min(t,max(i-k,0))
  k=i
ans+=t
print(ans)

Submission status: Runtime Error

Solution code:
N,T=map(int,input().split(' '))
times=[int(input()) for i in range(N)]
print(sum([min(T, times[i+1]-times[i] for i in range(N-1))])+times[-1])

Submission status: Runtime Error

Solution code:
N,T=map(int,input().split())
t=list(map(int,input().split()))

for i in range(0,len(t)-1):
        ans+=min(t[i+1]-t[i],T)
ans+=T
print(ans)

Submission status: Runtime Error

Solution code:
n, t = [int(x) for x in input().split(' ')]
time = [int(x) for x in input().split(' ')]

int ans = 0

for i = time:
    if i > t:
        ans += t
    else:
        ans += i

print(ans)

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())

items = [tuple(map(int,input().split())) for i in range(N)]

from collections import defaultdict
dp = defaultdict(int) # w -> v
dp[0] = 0

for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w <= W:
      dp[tw+w] = max(tv+v, dp[tw+w])

print(max(dp.values()))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

N, T = map(int, raw_input().split(' '))
t = map(int, raw_input().split(' '))
assert len(t) == N

begin = t[0]
end = t[0] + T
for i in range(N):
    if t[i] <= end:
        end = t[i] + T
    else:
        sum += (end - begin)
        begin = t[i]
        end = t[i] + T

sum += (end - begin)
print sum

Submission status: Runtime Error

Solution code:
def main():
    line=input()
    line=line.split(' ')
    n=line[0]
    t=line[1]
    line=input()
    line=line.split(' ')
    total=0
    for i in range(1,n):
        total+=min(t,line[i]-line[i-1])
    print(total)
    

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from itertools import izip


def sol(n, w, wis, vis):
    rv = 0
    best = dd(int)
    for i, (wi, vi) in enumerate(izip(wis, vis)):
        if wi < w:
            best[(wi, i)] = max(best[(wi, i)], vi)
            rv = max(vi, rv)

    frontline = [(i, wis[i], vis[i]) for i in xrange(n - 1, -1, -1)]
    while frontline:
        last, cw, cv = frontline.pop()
        for i in xrange(last + 1, n):
            nw, nv = cw + wis[i], cv + vis[i]
            if nw <= w and best[(nw, i)] < nv:
                best[(nw, i)] = nv
                frontline.append((i, nw, nv))
                rv = max(rv, nv)

    return rv


if __name__ == "__main__":
    n, w = map(int, raw_input().strip().split())
    wis, vis = [], []
    for _ in xrange(n):
        wi, vi = map(int, raw_input().strip().split())
        wis.append(wi)
        vis.append(vi)
    print sol(n, w, wis, vis)

Submission status: Runtime Error

Solution code:
#-*- coding: utf-8 -*-

def knapsack2(items, W):
    N = len(items)
    C = [[0 for _i in xrange(W+1)] for _j in xrange(N+1)]
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return C[-1][-1]


def input_str(row):
    res = []
    for _ in xrange(row):
        res.append(raw_input().split())
    return res


N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

Submission status: Runtime Error

Solution code:
#-*- coding: utf-8 -*-
def knapsack2(items, W):
    N = len(items)
    C = [[0 for _i in xrange(W+1)] for _j in xrange(N+1)]
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return C[-1][-1]

N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

Submission status: Runtime Error

Solution code:
n=int(raw_input())
xy=[]
for i in xrange(n):
    x,y=map(int,raw_input().split())
    if x>y:x,y=y,x
    xy.append((x,y))
xy.sort()
rmn=10**12;rmx=0;bmn=10**12;bmx=0
for i in xrange(n):
    x,y=xy[i]
    rmn=min(rmn,y)
    rmx=max(rmx,y)
    bmn=min(bmn,x)
    bmx=max(bmx,x)
ans1=(rmx-rmn)*(bmx-bmn)
cntmx=0;cntmn=0
for i in xrange(n):
    x,y=xy[i]
    if rmx==y:cntmx+=1
    if bmn==x:cntmx+=1
if cntmx==1 and cntmn==1 and xy[0][0]==bmn and xy[0][1]==rmx:
    print ans1
    exit()
xy[0]=(xy[0][1],xy[0][0])
xy.sort()
ymn=[10**12]*n
rmn=bmn;bmn=xy[0][0];bmx=xy[n-1][0]
for i in xrange(n):
    x,y=xy[i]
    ymn[i]=min(ymn[max(0,i-1)],y)
ans2=(rmx-rmn)*(bmx-bmn)
for i in xrange(1,n):
    x,y=xy[i]
    if ymn[i]<x:
        break
    bmn=x
    bmx=max(bmx,xy[i-1][1])
    ans2=min(ans2,(rmx-rmn)*(bmx-bmn))
print min(ans1,ans2)

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
mod = 10**9 + 7
 
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 main():
    n = I()
    a = sorted([sorted(LI()) + [_] for _ in range(n)])
    b = sorted(a, key=lambda x: x[1])
    r = (a[-1][0]-a[0][0]) * (b[-1][1]-b[0][1])
 
 
    bm = b[-1][1] - a[0][0]
    bmi = b[0][2]
    am = a[-1][1]
    at = 0
    k = [[inf,0]]
    for i in range(n-1):
        kk = []
        kk.append(min(k[-1][0], b[i][0], b[i+1][1]))
        kk.append(max(k[-1][1], b[i][0]))
        if kk[0] == k[-1][0]:
            k[-1][1] = kk[1]
        else:
            k.append(kk)
 
    k = k[1:]
    kl = len(k)
 
    am = b[-1][1] - a[0][0]
    ami = a[0][2]
    bm = 0
    mtm = 0
    bt = b[0][1]
 
    for i in range(n-1,0,-1):
        tm = b[i][0]
        if mtm < tm:
            mtm = tm
        if ami == b[i][2]:
            break
        if tm < bt:
            bt = tm
        if tm < b[i-1][1]:
            tm = b[i-1][1]
        bm = mtm
        if tm > bm:
            bm = tm
 
        tr = am * (bm-bt)
        if r > tr:
            r = tr
 
        for j in range(kl):
            ki,km = k[j]
            if km > bm:
                break
            tr = am * (bm-min(ki,bt))
            if r > tr:
                r = tr
 
    return r
 
 
print(main())

Submission status: Runtime Error

Solution code:
Rmax = 0
Rmin = 1000000000
Bmax = 0
Bmin = 1000000000

N = int(input())
xs = []
ys = []
arr = []
for i in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    arr.append((max(x, y) / min(x, y), min(x, y), max(x, y)))

arr = list(sorted(arr))
for (_, x, y) in arr:
    Rmin0 = min(Rmin, x)
    Rmax0 = max(Rmax, x)
    Bmin0 = min(Bmin, y)
    Bmax0 = max(Bmax, y)
    p0 = (Rmax0 - Rmin0) * (Bmax0 - Bmin0)
    Rmin1 = min(Rmin, y)
    Rmax1 = max(Rmax, y)
    Bmin1 = min(Bmin, x)
    Bmax1 = max(Bmax, x)
    p1 = (Rmax1 - Rmin1) * (Bmax1 - Bmin1)
    if p0 <= p1:
        Rmin = Rmin0
        Rmax = Rmax0
        Bmin = Bmin0
        Bmax = Bmax0
    else:
        Rmin = Rmin1
        Rmax = Rmax1
        Bmin = Bmin1
        Bmax = Bmax1

ans = (Rmax - Rmin) * (Bmax - Bmin)
print(ans)