• Source
    1. //INOI PRACTICE
    2.  
    3. #include <iostream>
    4.  
    5. using namespace std;
    6.  
    7. unsigned long npeople;
    8.  
    9. //return the UNBURNT i for which sum time is minimum
    10. unsigned long computemaxbursttime(unsigned long sumtime[], unsigned long burnt[], unsigned long coboltime[]);
    11.  
    12. int main()
    13. {
    14. cin>>npeople;
    15.  
    16. unsigned long *coboltime = new unsigned long [npeople+1];
    17. unsigned long *vaulttime = new unsigned long [npeople+1];
    18. unsigned long *eatingtime = new unsigned long [npeople+1];
    19. unsigned long *sumtime = new unsigned long [npeople+1];
    20. unsigned long *burnt = new unsigned long[npeople+1];
    21. unsigned long additionaltime = 0;
    22. unsigned long minrequiredtime = 0;
    23.  
    24. unsigned long i;
    25.  
    26. for(i = 1; i<=npeople; i++)
    27. {
    28. cin>>coboltime[i]>>vaulttime[i]>>eatingtime[i];
    29. sumtime[i] = vaulttime[i] + eatingtime[i];
    30. burnt[i] = 0;
    31. }
    32.  
    33. i = computemaxbursttime(sumtime, burnt, coboltime);
    34.  
    35. while(i)
    36. {
    37. burnt[i] = 1;
    38. minrequiredtime = sumtime[i] + additionaltime + coboltime[i];
    39. additionaltime += coboltime[i];
    40. i = computemaxbursttime(sumtime,burnt,coboltime);
    41. }
    42.  
    43. cout<<minrequiredtime;
    44.  
    45. return 0;
    46. }
    47.  
    48. unsigned long computemaxbursttime(unsigned long sumtime[], unsigned long burnt[], unsigned long coboltime[])
    49. {
    50. unsigned long pos = 0;
    51. unsigned long maxburst = 0;
    52.  
    53. for(unsigned long i = 1; i<=npeople; i++)
    54. {
    55. if(!burnt[i] && sumtime[i] >= maxburst)
    56. {
    57. if(sumtime[i]>maxburst)
    58. pos = i;
    59. else
    60. {
    61. if(coboltime[i]<coboltime[pos])
    62. pos = i;
    63. }
    64. }
    65. }
    66.  
    67. return pos;
    68. }