Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation

  • Binge watching

    Ben tries to maximize the time he watches movies. He knows that there are n movies that are going to be streamed on TV during the coming several days and he knows the duration of each movie. We know that Ben can only binge-watch movies for at most 5 hours (18000 seconds) and falls asleep after that. He only counts the movies that he watched from the beginning to the very end. So, if he falls asleep halfway through, that movie is not counted.
    notion image
    Can you help him with the decision on when to start watching, by showing how many seconds he will be able to watch fully if he starts watching from the i-th movie?

    Input

    The first line of the input contains the integer n the number of movies Ben knows are going to be streamed (1 ≀ n ≀ ). The following line contains n integers separated by a space, that represent the lengths of the movies in seconds .

    Output

    The program should print n integers. The number at position i should represent the number of seconds Ben would be able to fully watch if he starts at the movie i.

    Examples

    Input
    Output
    8 12000 3000 9000 12000 13200 13800 3600 5400
    15000 12000 9000 12000 13200 17400 9000 5400
    Β 

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue