Skip to content

12001: 【原2001】Sum of Subsequences

题目

题目描述

author: xjia 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2001

Description

Given a sequence of integers \( a_1, a_2, \dots, a_n \), calculate the sum of the subsequences \( a_i + a_2 + \dots + a_j \) with different pairs of \(i,j\) specified.

Input Format

Line 1: A positive integer \( n, 1 \leq n \leq 10000 \)

Line 2: A sequence of \(n\) integers \( a_1, a_2, \dots, a_n, \forall 1 \leq k \leq n, -10000 \leq a_k \leq 10000\)

Line 3: A positive integer \( m, 1 \leq m \leq 10000 \)

Line 4 to \( m+3 \): Two positive integers \(i, j, 1 \leq i \leq j \leq n\)

Output Format

Line 1 to \(m\): An integer representing the sum of the subsequence with the specified pair of \(i, j\)

Sample Input

5
1 3 4 2 5
2
2 4
1 3

Sample Output

9
8

Limits

Time limit: 1000ms, memory limit: 50000kb.

satgo1546's solution

#include <cstdio>
using namespace std;

int a_[10010];
int *const a = &a_[4];

int main(int argc, char *argv[]) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        a[i] += a[i - 1];
    }
    scanf("%d", &argc);
    while (argc--) {
        int i, j;
        scanf("%d%d", &i, &j);
        printf("%d\n", a[j - 1] - a[i - 2]);
    }
    return 0;
}