10954 - Add All
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10954 - Add All
Use a priority_queue.
Check input and AC output for thousands of problems on uDebug!
10954 time limit
i am getting time limit in 10954 .
I have tried it with priority queue and vector both. Some suggestions are badly needed.
Here are the codes:
Using Priority Queue:
Using Stack:


Using Priority Queue:
Code: Select all
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
using namespace std;
int main()
{
long long i,n,x,y,sum1,sum2;
while(cin>>n && n)
{
priority_queue<long long>q;
stack<long long>s;
while(n--)
{
cin>>x;
q.push(x);
}
sum1=0;
sum2=0;
while(q.size()!=1)
{
if(q.size()>2)
{
s.push(q.top());
q.pop();
}
else
{
x=q.top();
q.pop();
y=q.top();
q.pop();
sum1=x+y;
sum2=sum2+sum1;
q.push(sum1);
while(!s.empty())
{
q.push(s.top());
s.pop();
}
}
}
cout<<sum2<<endl;
/*FILE* fp;
fp=fopen("G:\\g_output10954.txt","w");
fprintf(fp,"%lld\n",sum2);*/
}
return 0;
}
Using Stack:
Code: Select all
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
long long i,n,x,y,sum1,sum2;
while(cin>>n && n)
{
vector<long long>v;
while(n--)
{
cin>>x;
v.push_back(x);
}
sum1=0;
sum2=0;
while(v.size()!=1)
{
sort(v.begin(),v.end());
x=v[0];
v.erase(v.begin()+0);
if(!v.empty())
{
y=v[0];
v.erase(v.begin()+0);
}
else
y=0;
sum1=x+y;
sum2=sum2+sum1;
v.push_back(sum1);
}
cout<<sum2<<endl;
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10954 time limit
Use just a priority_queue, you don't need a stack.
Check input and AC output for thousands of problems on uDebug!
Re: 10954 time limit
I just use a vector and at first got TLE.
then i optimize the code and get AC.
But it took 2.8 sec.Probably the worst runtime.


Re: 10954 - Add All
I am getting WA.I tested my output,but did not find any mistake.Please,anybody help me.Thanks in advance.Here is my code...
Code: Select all
got ac
Last edited by sampad74 on Thu Jul 24, 2014 4:45 am, edited 1 time in total.
Re: 10954 - Add All
I'd suggest you avoid using the "long" type in C/C++, since it behaves differently in different systems. In 32-bit systems it typically has 4-bytes, and in 64-bit systems it has 8. Consider if a 4-byte integer suffices to hold every possible answer for this problem.sampad74 wrote:I am getting WA.I tested my output,but did not find any mistake.Please,anybody help me.Thanks in advance.Here is my code...
Also, be careful with array overflows/underflows. Consider, for example, what happens when n=2 and this piece of code is executed:
Code: Select all
for (i = 2; i < n; i++)
a [i - 2] = a [i];
i = n - 3;
while (a [i] > key) // ....
Re: 10954 - Add All
lbv wrote--
Also, be careful with array overflows/underflows. Consider, for example, what happens when n=2 and this piece of code is executed:
for (i = 2; i < n; i++)
a = a ;
i = n - 3;
while (a > key) // ....
i changed my code..
Code: Select all
I changed long to long long int ,but got WA again.
Last edited by sampad74 on Thu Jul 24, 2014 4:44 am, edited 1 time in total.
Re: 10954 - Add All
Please post the full, latest version of your code. For people wanting to help you, combining code from different posts to keep track of the changes is not exactly funsampad74 wrote:i changed my code.. (..)
but got WA again.

Re: 10954 - Add All
sorry...Here is my code.Thanks..
Code: Select all
got ac
Last edited by sampad74 on Thu Jul 24, 2014 4:44 am, edited 1 time in total.
Re: 10954 - Add All
You must check your program for input in this thread. It fails on this one
It must be
Don't forget to remove your code after getting accepted. 
Change lineMartin Macko wrote:Not working for this one:Nazmul Quader Zinnuree wrote:OK, Noboby is giving me some I/O that i wanted in another mail.
Now, would you just plz run my code, and say where I'm wrong!!!My AC's output:Code: Select all
8 40952 13521 6223 42589 93489 22376 78730 38792 0
Code: Select all
899661
Code: Select all
while (a [i] > key) {
Code: Select all
while (i > 0 && a[i] > key) {

A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 10954 - Add All
My code gave right answer for the following test case before changing previous code at my computer
..i don't know why
...


Afterall,got AC.Thank you.8
40952 13521 6223 42589 93489 22376 78730 38792
0
My AC's output:
899661
Re: 10954 - Add All
It gives exact output for sample input and some other critical inputs. I don't know why this code gets WA. . . .
Code: Select all
#include <stdio.h>
int main()
{
long long int n,sum,cost,i,a[99999],j,b;
while(scanf("%lld",&n)==1&&n!=0)
{
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i;j++)
{
if(a[j]>a[j+1])
{
b=a[j];
a[j]=a[j+1];
a[j+1]=b;
}
}
}
sum=a[1],cost=0;
for(i=2;i<=n;i++)
{
sum=sum+a[i];
cost=cost+sum;
}
if(n==1)
cost=sum;
printf("%lld\n",cost);
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10954 - Add All
Input:Correct output 144
Code: Select all
6
9 9 9 9 9 9
0
Check input and AC output for thousands of problems on uDebug!
Re: 10954 - Add All
Please help me with sample input analysis:
For the 2nd sample input-
4
1 2 3 4
1+2=3, cost=3
3+3=6, cost=6
6+4=10, cost=10
Total= 19
So, for your input-
6
9 9 9 9 9 9
9 + 9=18, cost=18
18+9=27, cost=27
27+9=36, cost=36
36+9=45, cost=45
45+9=54, cost=54
Total=180
Shouldn't it be like that? How that can be 144?
For the 2nd sample input-
4
1 2 3 4
1+2=3, cost=3
3+3=6, cost=6
6+4=10, cost=10
Total= 19
So, for your input-
6
9 9 9 9 9 9
9 + 9=18, cost=18
18+9=27, cost=27
27+9=36, cost=36
36+9=45, cost=45
45+9=54, cost=54
Total=180
Shouldn't it be like that? How that can be 144?