ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 0549 A Traveler

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549


・解法
やるだけ問題です。

入力ではiとi+1の宿場町の距離間が与えられますが、前計算として出発地点から各宿場町までの距離をそれぞれ求めておくとあまり時間をかけずに解くことができます。


ソースコード

#include<cstdio>
#include<cstdlib>
 
static const int MOD = 100000;
int city[100000];
 
int main(){
  int n,m;
  scanf("%d%d",&n,&m);
  city[0] = 0;
  for(int i = 1 ; i < n ; i++){
    int dist;
    scanf("%d",&dist);
    city[i] = city[i-1] + dist;
  }
  int ans = 0;
  int pos = 0;
  for(int i = 0 ; i < m ; i++){
    int a;
    scanf("%d",&a);
    if(a > 0) ans = (ans + city[a + pos] - city[pos]) % MOD;
    else ans = (ans + abs(city[pos] - city[pos + a])) % MOD;
    pos += a;
  }
  printf("%d\n",ans);
  return 0;  
}