In this problem, sum can be as large as 50000*10^9.
Try breaking the whole interval into several stages (no more than 2*N),
each with a fixed amount of tasks.
Then in each stage, the schedule is a simple loop: A B C D E A B C D E A
B ...
Process each stage in O(1) time, then the total time complexity is O(N).
On 2011-3-21 17:32, saurabh singh wrote:
using scanf and printf and still tle,I am not pretty sure how malloc
or new arrays can speed up execution?
On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal <[email protected]
<mailto:[email protected]>> wrote:
use scanf n printf instead of cin n cout,
malloc array of structures after reading value of n if working in
c else use new in cpp
rest i guess...is ok
On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal
<[email protected] <mailto:[email protected]>> wrote:
I worked on this problem but cud not get a more efficient algo
than yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma
<[email protected] <mailto:[email protected]>>
wrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#include<iostream>
#include<stdio.h>
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cin>>n;
struct process prss[50000];
for(long i=0;i<n;i++)
{
scanf("%ld",&prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k<=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;i<n;i++)
printf("%ld\n",prss[i].elapsed_time);
return 0;
}
--
You received this message because you are subscribed to
the Google Groups "Algorithm Geeks" group.
To post to this group, send email to
[email protected]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the
Google Groups "Algorithm Geeks" group.
To post to this group, send email to
[email protected] <mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
