D - Distance Table Editorial by en_translator
For each pair of integers \((i,j)\), the distance between station \(i\) and station \(j\) can be found as \(D_i+D_{i+1}+\cdots+D_{j-1}\), which can be computed with a for
statement.
A naive implementation will require a triple loop, which is fast enough under the constraints of this problem.
The algorithm can be made faster by reducing it to a double loop, using the fact that the distance between stations \(i\) and \(j\) can be calculated as \(S_j-S_i\), where \(S_k=D_1+D_2+\cdots+D_{k-1}\) is the distance between station \(1\) and station \(k\).
Sample code in C++ (triple loop):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
vector<int>d(n-1);
for(int i=0;i<n-1;i++){
cin>>d[i];
}
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
int ans = 0;
for(int k=i;k<j;k++)ans+=d[k];
cout << ans;
if(j<(n-1))cout << " ";
else cout << endl;
}
}
return 0;
}
Sample code in C++ (double loop):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
vector<int>s(n);
for(int i=1;i<n;i++){
cin>>s[i];
s[i]+=s[i-1];
}
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
cout<<(s[j]-s[i]);
if(j<(n-1))cout<<" ";
else cout<<endl;
}
}
return 0;
}
Sample code in Python (triple loop):
n=int(input())
d=list(map(int, input().split()))
for i in range(n-1):
for j in range(i+1,n):
if j<n-1:
print(sum(d[i:j]),end=' ')
else:
print(sum(d[i:j]))
posted:
last update: