In this HackerEarth Group Photo problem solution, You and your friends want to take group photos. The process of taking photos can be described as follows:
On the photo, each photographed friend occupies a rectangle of pixels: the ith of them occupies the rectangle of width wi pixels and height hi pixels. On the group photo everybody stands in a line, thus the minimum pixel size of the photo including all the photographed friends is W * H, where W is the total sum of all widths and H is the maximum height among the heights of all the photographed friends.
The friends made n photos - the jth (1 <= j <= n) photo had everybody except for the jth friend as he was the photographer.
Print the minimum size of each made photo in pixels.
HackerEarth Group Photo problem solution.
#include<bits/stdc++.h>
using namespace std ;
#define pb push_back
#define mp make_pair
#define infile() freopen("sample.txt","r",stdin);
#define output() freopen("sampleout.txt","w",stdout);
#define ll long long
#define sc(t); scanf("%d",&t);
#define scl(t); scanf("%lld",&t);
#define sc2(n,m); scanf("%d%d",&n,&m);
#define scl2(n,m); scanf("%lld%lld",&n,&m);
#define debug(); printf("tushar\n");
#define N 200005
#define mod 1000000007
#define printi(n) printf("%d",n);
vector < ll > v ;
int n ;
int a[N] ;
int w[N],h[N];
int main()
{
int i , j , t ;
sc(n) ;
multiset < int > s ;
multiset < int > :: iterator it ;
ll sum = 0LL;
for(i=1;i<=n;i++)
{
scanf("%d %d",&w[i],&h[i]) ;
sum = (ll)(sum + w[i]) ;
s.insert(h[i]) ;
}
for(i = 1 ; i <= n ; i++ )
{
ll tmp = (ll)(sum - w[i]) ;
it = s.find(h[i]) ;
s.erase(it) ;
it = s.end() ;
it-- ;
ll ans = (ll)(tmp * (*it)) ;
printf("%lld ",ans);
s.insert(h[i]);
}
return 0 ;
}
Second solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int w[200005],h[200005],cpy[200005];
int sum=0;
assert(n>=1 && n<=2e5);
for(int i=0;i<n;i++)
{
cin>>w[i]>>h[i];
sum+=w[i];
cpy[i]=h[i];
assert(w[i]>=1 && w[i]<=10);assert(h[i]>=1 && h[i]<=1e3);
}
if(n==1){cout<<"0\n";return 0;}
sort(cpy,cpy+n);
for(int i=0;i<n;i++)
{
int wgt=sum-w[i];
int hgt=(cpy[n-1]==h[i])?cpy[n-2]:cpy[n-1];
cout<<wgt*hgt<<" ";
}
return 0;
}
0 Comments