AOJ 0549: A Traveler
特定の区間に足し算をするのを高速(全体でO(n+m)くらい)に行えば良いから、累積和で解くことができます。
#include<cstdio> #include<algorithm> using namespace std; #define MOD 100000 int inn[100000],walk[100001]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i = 0; i < n-1; i++){ scanf("%d",inn+i); } int from,to = 0,ans = 0; for(int i = 0; i < m; i++){ from = to; int a; scanf("%d",&a); to += a; walk[min(from,to)]++; walk[max(from,to)]--; } for(int i = 0,sum = 0; i < n-1; i++){ sum += walk[i]; walk[i] = sum; ans = (ans + sum*inn[i]) % MOD; } printf("%d\n",ans); return 0; }