This problem is from [CCC2019]: https://dmoj.ca/problem/ccc19s5/ (Canadian Computing Contest 2019) and I have implemented it in C++.
I used sequence [A054237]: https://oeis.org/A054237/table to compute the indexes of sub-triangles.
In a parallel universe, the most important data structure in computer science is the triangle. A triangle of size M M consists of M M rows, with the i t h i^{th} row containing i i elements. Furthermore, these rows must be arranged to form the shape of an equilateral triangle. That is, each row is centred around a vertical line of symmetry through the middle of the triangle. For example, the diagram below shows a triangle of size 4:
A triangle contains sub-triangles. For example, the triangle above contains ten sub-triangles of size 1, six sub-triangles of size 2 (two of which are the triangle containing ( 3 , 1 , 2 ) (3,1,2) and the triangle containing ( 4 , 6 , 1 ) (4,6,1) ), three sub-triangles of size 3 (one of which contains ( 2 , 2 , 1 , 1 , 4 , 2 ) (2,2,1,1,4,2) ). Note that every triangle is a sub-triangle of itself.
You are given a triangle of size N N and must find the sum of the maximum elements of every sub-triangle of size K K .
Please review and suggest edits.
#include<stdio.h> int rec(int x) { return (x*(x+1))/2; //sum of n natural numbers } int main() { int n,k; //n=height of triangle k=height of sub-triangles ne= number of elements int t1=0; int t2=0; std::scanf("%d %d",&n,&k); int ne=rec(n); int rk=rec(k); //rk=number of elements in sub-triangle int nt=ne-rk-1; //ior[]=array to store index of row nt=number of sub-triangles unsigned long int e[ne],gval,sum=0; //e[]=array to store elements gval=greatest element of sub-triangle sum=sum of gvals gval=0; for(int i=0;i<ne;i++) scanf("%ld",&e[i]); for(int rt=0,ior=0;ior<nt;rt++) { for(int ioc,r=0; r<=rt && ior<nt; r++,ior++) { ioc=0; for(int ct=0;ioc<rk;ct++) { for(int c=0;c<=ct && ioc<rk;ioc++,c++,t2++) { if(gval<e[t2])gval=e[t2]; } t2+=rt; } sum+=gval; t1++; t2=t1; gval=0; } } std::printf("%ld",sum); return 0; }
using namespace std;, which is discouraged anyways. \$\endgroup\$using namespace std;read up here please. \$\endgroup\$