Problem:


旅人

  問題

あなたは JOI 街道を旅する旅人である.JOI 街道は東西にまっすぐに延びた道路で,JOI 街道上には n 個の宿場町がある.宿場町には西から東の順に 1 から n までの番号が付けられている.JOI 街道上の最も西の宿場町が宿場町 1 であり,最も東の宿場町が宿場町 n である.

あなたは,宿場町 1 から出発して m 日間の旅に出ることになった.あなたの旅程は数列 a1 , a2 , . . . , am に従い,次のように決められている.ai は i 日目の移動方法を表す 0 ではない整数である.i 日目にあなたが出発する宿場町を宿場町 k とおくと,i 日目にあなたは宿場町 k から宿場町 k + ai までまっすぐに移動することを意味する.

宿場町の個数 n,旅の日数 m,宿場町間の距離の情報と,移動方法を表す数列a1 , a2 , . . . , am が与えられたとき,m 日間の旅におけるあなたの移動距離の合計を100000 = 105 で割った余りを求めるプログラムを作成せよ.

入出力の例に対応する図

入力

1 行目には整数 n, m が空白区切りで書かれている.n (2 ≤ n ≤ 100000 = 105 ) はJOI 街道上の宿場町の個数を,m (1 ≤ m ≤ 100000 = 105 ) は旅の日数を表す.

続く n − 1 行は JOI 街道上の宿場町間の距離を表す.i + 1 行目 (1 ≤ i ≤ n − 1) に
は宿場町 i と宿場町 i + 1 の距離を表す正整数 si (1 ≤ si ≤ 100) が書かれている.

続く m 行には m 日間の移動方法を表す数列が書かれている.i + n 行目 (1 ≤ i ≤ m)
には i 日目のあなたの移動方法を表す 0 ではない整数 ai が書かれている.

採点用データにおいて,宿場町 1 より西に移動することや,宿場町 n より東に移
動することはない.

採点用データのうち,配点の 50% 分については,n ≤ 100 かつ m ≤ 100 を満たす.

 出力

出力 は, m 日間の旅におけるあなたの移動距離の合計を 100000 = 105 で割った余りを含む 1 行からなる.

 入出力例

入力例 1
  

7 5
2
1
1
3
2
1
2
-1
3
2
-3

出力例 1

18

1 日目に,あなたは宿場町 1 から宿場町 3 まで移動する.2 日目に,あなたは宿場
町 3 から宿場町 2 まで移動する.そして,3 日目に宿場町 2 から宿場町 5 まで移動
し,4 日目に宿場町 5 から宿場町 7 まで移動し,5 日目に宿場町 7 から宿場町 4 ま
で移動する.5 日間の旅におけるあなたの移動距離の合計は 18 である.

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
7 5
2
1
1
3
2
1
2
-1
3
2
-3


Sample output:
18

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())

accums = [0]
for i in range(n - 1):
    accums.append(accums[-1] + int(input()))

result = 0
k = 0
for i in range(m):
    a = int(input())
    result += abs(accums[k + a] - accums[k])
    k += a

print(result % 10000)

Submission status: Wrong Answer

Solution code:
DIV = 100000
n, m = map(int, raw_input().split())
l = [input() for _ in range(n-1)]
ans = [0]*(n-1)
pos = 0
for _ in range(m):
    k = input()
    if k > 0:
        for i in range(k): ans[pos+i] += 1
    else:
        for i in range(-1, k-1, -1):       
            ans[pos+i] += 1
    pos += k
print sum((ans[i] * l[i]) % DIV for i in range(n-1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created: 木 11/ 9 19:01:14 2017

# Usage
#
"""
from itertools import accumulate

def data_req():
    n_yado, m_ryotei = [int(i) for i in input().split(" ")]
    yado_distance = []
    ryotei = []
    for _ in range(n_yado - 1):
        yado_distance.append(int(input()))
    for _ in range(m_ryotei):
        ryotei.append(int(input()))

    return yado_distance, ryotei


def search(distance, ryotei):
    """search.

    >>> search([2, 1, 1, 3, 2, 1], [2, -1, 3, 2, -3])
    18
    """
    acc = [0] + list(accumulate(distance, lambda x, y: x+y))
    ryotei_index = [0] + list(accumulate(ryotei, lambda x, y: x+y))
    # print(ryotei_index)
    res = []
    for index in enumerate(ryotei_index):
        if index[0] == 0:
            continue
        index = index[0]
        # print(index)
        # print(ryotei_index[index])
        # print(ryotei_index[index - 1])
        dist = abs(acc[ryotei_index[index]] - acc[ryotei_index[index - 1]])
        res.append(dist)
        # print(sum(res))
    # his = []
    #
    # for index in range(len(ryotei_index)):
    #     his.append(acc[ryotei_index[index + 1]] - acc[ryotei_index[index]])
    #
    # return sum(his)
    return sum(res)


if __name__ == '__main__':
    dis, ryotei = data_req()
    search(dis, ryotei)

Submission status: Wrong Answer

Solution code:

NM=input().split()

N=int(NM[0])
M=int(NM[1])

s=[]
a=[]

for i in range(N-1):
    s.append(int(input()))

Sum=0
TotalS=[0]

for i in range(N-1):
    Sum+=s[i]
    TotalS.append(Sum)

position=0
TD=0

for i in range(M):
    a=int(input())
    TD+=abs(TotalS[position]-TotalS[position+a])
    position+=a

print(TD)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split(' '))

dist_sum = [0] * n
for x in xrange(n - 1):
    d = int(raw_input())
    dist_sum[x + 1] = dist_sum[x] + d

ans = 0
cur = 0

for x in xrange(m):
    k = int(raw_input())
    ans += abs(dist_sum[cur + k] - dist_sum[cur])
    cur += k

print ans

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

accums = [0]
for i in range(n - 1):
    accums.append(accums[-1] + int(input()))

result = 0
k = 0
for i in range(m):
    a = int(input())
    result += abs(accums[k + a] - accums[k])
    k += a

print(result % 100000)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

accums = [0]
for i in range(n - 1):
    accums.append(accums[-1] + int(input()))

result = 0
k = 0
for i in range(m):
    a = int(input())
    result = (result + abs(accums[k + a] - accums[k])) % 100000
    k += a

print(result)

Submission status: Accepted

Solution code:
DIV = 100000
n, m = map(int, raw_input().split())
l = [0]*n
for i in range(n-1):
    k = input()
    l[i+1] = l[i] + k
ans = pos = 0
for _ in xrange(m):
    k = input()
    ans = (ans + abs(l[pos + k] - l[pos])) % DIV
    pos += k
print ans

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]
for _ in range(n-1):a+=[a[-1]+int(input())]
ans=b=0
for _ in range(m):
    c=int(input())
    ans+=abs(a[b+c]-a[b])
    b+=c
print(ans%10**5)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
kyori = [0 for _ in range(n + 1)]
cum_k = [0 for _ in range(n + 1)]
for ni in range(1, n):
    si = int(input())
    kyori[ni] = si
    cum_k[ni + 1] = cum_k[ni] + si
# print(kyori)
# print(cum_k)
ans, pos = 0, 1
for mi in range(m):
    nex = pos + int(input())
    ans += abs(cum_k[nex] - cum_k[pos])
    pos = nex
print(ans % 100000)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
lng = [0]
for _ in range(n-1):
    lng.append(lng[-1] + int(input()))
i = 0
sm = 0
for _ in range(m):
    j = i+int(input())
    sm += abs(lng[i]-lng[j])
    sm %= 100000
    i = j
print(sm)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549

"""
import sys
from sys import stdin
from itertools import accumulate
input = stdin.readline




def main(args):
    n, m = map(int, input().split())
    distances = [int(input()) for _ in range(n-1)]
    inns = list(accumulate(distances))
    moves = [int(input()) for _ in range(m)]

    inns.insert(0, 0)
    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549
AC
"""
import sys
from sys import stdin
from itertools import accumulate
input = stdin.readline
import array

def main(args):
    n, m = map(int, input().split())
    distances = [int(input()) for _ in range(n-1)]
    inns = list(accumulate(distances))
    moves = [int(input()) for _ in range(m)]

    inns.insert(0, 0)
    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)



def main2(args):
    n, m = map(int, input().split())

    pos = 0
    inns = array.array('Q', [0])
    for _ in range(n-1):
        pos += int(input())
        inns.append(pos)
    moves = [int(input()) for _ in range(m)]

    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)



if __name__ == '__main__':
    main2(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549
AC
"""
import sys
from sys import stdin
from itertools import accumulate
input = stdin.readline
import array

def main(args):
    n, m = map(int, input().split())
    distances = [int(input()) for _ in range(n-1)]
    inns = list(accumulate(distances))
    moves = [int(input()) for _ in range(m)]

    inns.insert(0, 0)
    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)



def main2(args):
    n, m = map(int, input().split())

    pos = 0
    inns = array.array('Q', [0])
    for _ in range(n-1):
        pos += int(input())
        inns.append(pos)
    moves = [int(input()) for _ in range(m)]

    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)



def main3(args):
    n, m = map(int, input().split())

    pos = 0
    inns = {0: 0}
    for i in range(n-1):
        pos += int(input())
        inns[i+1] = pos
    moves = [int(input()) for _ in range(m)]

    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)



if __name__ == '__main__':
    main3(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549
AC
"""
import sys
from sys import stdin
from itertools import accumulate
input = stdin.readline
import array

def main(args):
    # list
    n, m = map(int, input().split())
    distances = [int(input()) for _ in range(n-1)]
    inns = list(accumulate(distances))
    moves = [int(input()) for _ in range(m)]

    inns.insert(0, 0)
    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)



def main2(args):
    # array
    n, m = map(int, input().split())

    pos = 0
    inns = array.array('L', [0])
    for _ in range(n-1):
        pos += int(input())
        inns.append(pos)
    moves = [int(input()) for _ in range(m)]

    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)



def main3(args):
    # dict
    n, m = map(int, input().split())

    pos = 0
    inns = {0: 0}
    for i in range(n-1):
        pos += int(input())
        inns[i+1] = pos
    moves = [int(input()) for _ in range(m)]

    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)



if __name__ == '__main__':
    main2(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created: 木 11/ 9 19:01:14 2017

# Usage
#
"""
from itertools import accumulate

def data_req():
    n_yado, m_ryotei = [int(i) for i in input().split(" ")]
    yado_distance = []
    ryotei = []
    for _ in range(n_yado - 1):
        yado_distance.append(int(input()))
    for _ in range(m_ryotei):
        ryotei.append(int(input()))

    return yado_distance, ryotei


def search(distance, ryotei):
    """search.

    >>> search([2, 1, 1, 3, 2, 1], [2, -1, 3, 2, -3])
    18
    """
    acc = [0] + list(accumulate(distance, lambda x, y: x+y))
    ryotei_index = [0] + list(accumulate(ryotei, lambda x, y: x+y))
    # print(ryotei_index)
    res = []
    for index in enumerate(ryotei_index):
        if index[0] == 0:
            continue
        index = index[0]
        # print(index)
        # print(ryotei_index[index])
        # print(ryotei_index[index - 1])
        dist = abs(acc[ryotei_index[index]] - acc[ryotei_index[index - 1]])
        res.append(dist)
        # print(sum(res))
    # his = []
    #
    # for index in range(len(ryotei_index)):
    #     his.append(acc[ryotei_index[index + 1]] - acc[ryotei_index[index]])
    #
    # return sum(his)
    return sum(res)


if __name__ == '__main__':
    dis, ryotei = data_req()
    print(search(dis, ryotei) % 100000)

Submission status: Accepted

Solution code:

NM=input().split()

N=int(NM[0])
M=int(NM[1])

s=[]
a=[]

for i in range(N-1):
    s.append(int(input()))

Sum=0
TotalS=[0]

for i in range(N-1):
    Sum+=s[i]
    TotalS.append(Sum)

position=0
TD=0#TraveledDistance

for i in range(M):
    a=int(input())
    TD+=abs(TotalS[position]-TotalS[position+a])
    position+=a

TD%=100000
print(TD)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
lst = [0]
for i in range(n - 1):
  lst.append(lst[-1] + int(input()))
ans = 0
num = 0
for i in range(m):
  a = int(input())
  ans += abs(lst[num] - lst[num + a])
  ans %= 100000
  num += a
print(ans)

Submission status: Accepted

Solution code:
def solve():
  n,m = map(int,input().split())
  lst = [0]
  for i in range(n - 1):
    lst.append(lst[-1] + int(input()))
  ans = 0
  num = 0
  for i in range(m):
    a = int(input())
    ans += abs(lst[num] - lst[num + a])
    num += a
  print(ans % 100000)
solve()

Submission status: Accepted

Solution code:
def solve():
  n,m = map(int,input().split())
  lst = [0]
  append = lst.append
  for i in range(n - 1):
    append(lst[-1] + int(input()))
  ans = 0
  num = 0
  for i in range(m):
    a = int(input())
    ans += abs(lst[num] - lst[num + a])
    num += a
  print(ans % 100000)
solve()

Submission status: Accepted

Solution code:
# AOJ 0549: A Traveler
# Python3 2018.7.1 bal4u

import sys
from sys import stdin
input = stdin.readline

M, BigM = 100000, 1000000000

n, m = map(int, input().split())
s = [0]*(n+1)
for i in range(2, n+1): s[i] = s[i-1] + int(input())
ans, p1 = 0, 1
for i in range(m):
	p2 = p1 + int(input())
	x = s[p2] - s[p1]
	if x >= 0: ans += x
	else:      ans -= x
	if ans >= BigM: ans %= M
	p1 = p2;
print(ans % M)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split(' '))

dist_sum = [0] * n
for x in xrange(n - 1):
    d = int(raw_input())
    dist_sum[x + 1] = dist_sum[x] + d

ans = 0
cur = 0

for x in xrange(m):
    k = int(raw_input())
    ans += abs(dist_sum[cur + k] - dist_sum[cur])
    ans %= 10 ** 5
    cur += k

print ans

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
dist = [0]
MOD = 10**5
for _ in range(N-1):
  d = int(input())
  dist.append(d)

for i in range(N-1):
  dist[i+1] += dist[i]

res = 0
cur = 0
for _ in range(M):
  a = int(input())
  res += abs(dist[cur+a] - dist[cur]) % MOD
  cur = cur+a

print(res%MOD)

Submission status: Accepted

Solution code:
from itertools import accumulate

def main():
    ans = 0
    n, m = map(int,input().split())
    cost = [int(input()) for _ in range(n - 1)]
    q = [int(input()) for _ in range(m)]
    cumsum = list(accumulate(cost))
    cumsum.insert(0,0)
    index = 0
    for i in range(m):
        ans += abs(cumsum[index] - cumsum[index + q[i]])
        index += q[i]
    print(ans%10**5)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
DIV = 100000
n, m = map(int, raw_input().split())
l = [input() for _ in range(n-1)]
ans = [0]*(n-1)
pos = 0
for _ in range(m):
    k = input()
    if k > 0:
        for i in range(k): ans[pos+i] += 1
    else:
        for i in range(-1, k-1, -1):       
            ans[pos+i] += 1
    pos += k
print sum((ans[i] * l[i]) % DIV for i in range(n-1)) % DIV

Submission status: Runtime Error

Solution code:
DIV = 100000
n, m = map(int, raw_input().split())
l = [input() for _ in range(n-1)]
ans = [0]*(n-1)
pos = 0
for _ in xrange(m):
    k = input()
    if k > 0:
        for i in xrange(k): ans[pos+i] += 1
    else:
        for i in xrange(-1, k-1, -1):       
            ans[pos+i] += 1
    pos += k
print sum((ans[i] * l[i]) % DIV for i in xrange(n-1)) % DIV

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
lng = []
for _ in range(n-1):
    lng.append(int(input()))
i = 0
sm = 0
for _ in range(m):
    j = i+int(input())
    mv = sum(lng[i:j]) if j > i else sum(lng[j:i])
    sm += mv
    i = j
print(sm%100000)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
lng = []
for _ in range(n-1):
    lng.append(int(input()))
i = 0
sm = 0
for _ in range(m):
    j = i+int(input())
    mv = sum(lng[i:j]) if j > i else sum(lng[j:i])
    sm += mv
    if sm >= 100000: sm -= 100000
    i = j
print(sm)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
lng = []
for _ in range(n-1):
    lng.append(int(input()))
i = 0
sm = 0
for _ in range(m):
    j = i+int(input())
    mv = sum(lng[i:j]) if j > i else sum(lng[j:i])
    sm += mv
    sm %= 100000
    i = j
print(sm)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created: 木 11/ 9 19:01:14 2017

# Usage
#
"""
from itertools import accumulate

def data_req():
    n_yado, m_ryotei = [int(i) for i in input().split(" ")]
    yado_distance = []
    ryotei = []
    for _ in range(n_yado):
        yado_distance.append(int(input()))
    for _ in range(m_ryotei):
        ryotei.append(int(input()))

    return yado_distance, ryotei


def search(distance, ryotei):
    """search.

    >>> search([2, 1, 1, 3, 2, 1], [2, -1, 3, 2, -3])
    18
    """
    acc = [0] + list(accumulate(distance, lambda x, y: x+y))
    ryotei_index = [0] + list(accumulate(ryotei, lambda x, y: x+y))
    # print(ryotei_index)
    res = []
    for index in enumerate(ryotei_index):
        if index[0] == 0:
            continue
        index = index[0]
        # print(index)
        # print(ryotei_index[index])
        # print(ryotei_index[index - 1])
        dist = abs(acc[ryotei_index[index]] - acc[ryotei_index[index - 1]])
        res.append(dist)
        # print(sum(res))
    # his = []
    #
    # for index in range(len(ryotei_index)):
    #     his.append(acc[ryotei_index[index + 1]] - acc[ryotei_index[index]])
    #
    # return sum(his)
    return sum(res)


if __name__ == '__main__':
    dis, ryotei = data_req()
    search(dis, ryotei)

Submission status: Runtime Error

Solution code:
#include <stdio.h>

int main() {
    int i;
    int n, m, now_pos, sum;
    int s[100000]; 
    int imos[100000];

    scanf("%d %d", &n, &m);
    for (i=0;i<n-1;i++) {
        scanf("%d", &s[i]);
    }

    now_pos = 0;
    for (i=0;i<m;i++) {
        int a;

        scanf("%d", &a);

        if (a < 0) {
            imos[now_pos] -= 1;
            imos[now_pos+a] += 1;
        } else {
            imos[now_pos] += 1;
            imos[now_pos+a] -= 1;
        }

        now_pos += a;
    }

    sum = imos[0] * s[0];
    for (i=1;i<n;i++) {
        imos[i] += imos[i-1];
        sum += imos[i] * s[i];
    }

    printf("%d\n", sum);
}