Zonal Computing Olympiad 2014, 30 Nov 2013

In ICO School, all students have to participate regularly in SUPW.  There is a different SUPW activity each day, and each activity has its own duration.  The SUPW schedule for the next term has been announced, including information about the number of minutes taken by each activity.

Nikhil has been designated SUPW coordinator.  His task is to assign SUPW duties to students, including himself.  The school's rules say that no student can go three days in a row without any SUPW duty.

Nikhil wants to find an assignment of SUPW duty for himself that minimizes the number of minutes he spends overall on SUPW.

-----Input format-----
Line 1: A single integer N, the number of days in the future for which SUPW data is available.
Line 2: N non-negative integers, where the integer in position i represents the number of minutes required for SUPW work on day i.

-----Output format-----
The output consists of a single non-negative integer, the minimum number of minutes that Nikhil needs to spend on SUPW duties this term 

-----Sample Input 1-----
10
3 2 1 1 2 3 1 3 2 1

-----Sample Output 1-----
4

(Explanation: 1+1+1+1)

-----Sample Input 2-----
8
3 2 3 2 3 5 1 3

-----Sample Output 2-----
5

(Explanation: 2+2+1)

-----Test data-----
There is only one subtask worth 100 marks.  In all inputs:

• 1 ≤ N ≤ 2×105
• The number of minutes of SUPW each day is between 0 and
104, inclusive.

-----Live evaluation data-----
There are 12 test inputs on the server during the exam.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from sys import stdin,stdout\r\ndef fn(pos):\r\n    if pos>=n:return 0\r\n    if pos in dp:return dp[pos]\r\n    op1=op2=op3=float('inf')\r\n    op1=a[pos]+fn(pos+3)\r\n    if pos+1<n:op2=a[pos+1]+fn(pos+3)\r\n    if pos+2<n:op3=a[pos+2]+fn(pos+3)\r\n    dp[pos]=min(op1,op2,op3)\r\n    return dp[pos]\r\nfor _ in range(1):#int(stdin.readline())):\r\n    n=int(stdin.readline())\r\n    a=list(map(int,stdin.readline().split()))\r\n    # print(dp)\r\n    dp=[0]*n\r\n    dp[0]=a[0]\r\n    if n==1:\r\n        print(dp[0])\r\n        continue\r\n    dp[1]=a[1]\r\n    if n==2:\r\n        print(min(dp))\r\n        continue\r\n    dp[2]=a[2]\r\n    if n==3:\r\n        print(min(dp))\r\n        continue\r\n    for i in range(3,n):\r\n        dp[i]=min(dp[i-3],dp[i-1],dp[i-2])+a[i]\r\n    print(min(dp[-1],dp[-2],dp[-3]))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13673