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\$ – πάντα ῥεῖ Sep 29 '19 at 11:11using namespace std;
read up here please. \$\endgroup\$ – πάντα ῥεῖ Sep 29 '19 at 11:19