{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e.content-description h4 {\n font-size: 1.4em;\n border-bottom: 1px solid #eee;\n line-height: 1.225;\n padding-bottom: 0.3em;\n padding-top: 0.5em;\n font-weight: 700;\n}.content-description img {\n max-width: 100%;\n height: auto;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content-description screen\"\u003e\n\u003cdiv\u003e\u003cp\u003eJian-Jia is planning his next holiday in Taiwan. During his holiday, Jian-Jia moves from city to city and visits attractions in the cities.\u003c/p\u003e\n\u003cp\u003eThere are \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e cities in Taiwan, all located along a single highway. The cities are numbered consecutively from 0 to \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a8f3ffb97a067d57b3b70f6fc7c877c5?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:5.397ex; height:2.343ex;\" alt\u003d\"n-1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n-1~\u003c/span\u003e\u003c/span\u003e. For city \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e, where \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/61b9613adedb75f8397b1576895cd3e7?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:13.56ex; height:2.343ex;\" alt\u003d\"0 \u003c i \u003c n-1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \u0026lt; i \u0026lt; n-1~\u003c/span\u003e\u003c/span\u003e, the adjacent cities are \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/74a1ee0a08e34bf3b06fc5affc99bd4b?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:4.805ex; height:2.343ex;\" alt\u003d\"i-1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i-1~\u003c/span\u003e\u003c/span\u003e and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/cc2bcc2c55ce63f71474bdd25445dabc?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:4.805ex; height:2.343ex;\" alt\u003d\"i+1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i+1~\u003c/span\u003e\u003c/span\u003e. The only city adjacent to city 0 is city 1, and the only city adjacent to city \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a8f3ffb97a067d57b3b70f6fc7c877c5?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:5.397ex; height:2.343ex;\" alt\u003d\"n-1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n-1~\u003c/span\u003e\u003c/span\u003e is city \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/b2c01398f3e8a804c0cc9b3d7ab14032?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:5.397ex; height:2.343ex;\" alt\u003d\"n-2\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n-2~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eEach city contains some number of attractions. Jian-Jia has \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0c35b246884fa5dfec837b15a90157e7?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:1.216ex; height:2.176ex;\" alt\u003d\"d\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~d~\u003c/span\u003e\u003c/span\u003e days of holiday and plans to visit as many attractions as possible. Jian-Jia has already selected a city in which to start his holiday. In each day of his holiday Jian-Jia can either move to an adjacent city, or else visit all the attractions of the city he is staying, but not both. Jian-Jia will \u003cem\u003enever visit the attractions in the same city twice\u003c/em\u003e even if he stays in the city multiple times. Please help Jian-Jia plan his holiday so that he visits as many different attractions as possible.\u003c/p\u003e\n\u003ch4\u003eExample\u003c/h4\u003e\n\u003cp\u003eSuppose Jian-Jia has 7 days of holiday, there are 5 cities (listed in the table below), and he starts from city 2. On the first day Jian-Jia visits the 20 attractions in city 2. On the second day Jian-Jia moves from city 2 to city 3, and on the third day visits the 30 attractions in city 3. Jian-Jia then spends the next three days moving from city 3 to city 0, and visits the 10 attractions in city 0 on the seventh day. The total number of attractions Jian-Jia visits is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/5650b12c13ea24373a5ad676d0a8c473?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:18.079ex; height:2.343ex;\" alt\u003d\"20 + 30 + 10 \u003d 60\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~20 + 30 + 10 \u003d 60~\u003c/span\u003e\u003c/span\u003e, which is the maximum number of attractions Jian-Jia can visit in 7 days when he starts from city 2.\u003c/p\u003e\n\u003ctable class\u003d\"table\" style\u003d\"max-width: 18em;\"\u003e\n\u003ctbody\u003e\u003ctr\u003e\u003cth\u003ecity\u003c/th\u003e\u003cth\u003enumber of attractions\u003c/th\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e10\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e2\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003e20\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003e30\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e4\u003c/td\u003e\u003ctd\u003e1\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003ctable class\u003d\"table\" style\u003d\"max-width: 20em;\"\u003e\n\u003ctbody\u003e\u003ctr\u003e\u003cth\u003eday\u003c/th\u003e\u003cth\u003eaction\u003c/th\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003evisit the attractions in city 2\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003emove from city 2 to city 3\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003evisit the attractions in city 3\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e4\u003c/td\u003e\u003ctd\u003emove from city 3 to city 2\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e5\u003c/td\u003e\u003ctd\u003emove from city 2 to city 1\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e6\u003c/td\u003e\u003ctd\u003emove from city 1 to city 0\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e7\u003c/td\u003e\u003ctd\u003evisit the attractions in city 0\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003ch4\u003eTask\u003c/h4\u003e\n\u003cp\u003ePlease implement a function \u003ccode\u003efindMaxAttraction\u003c/code\u003e that computes the maximum number of attractions Jian-Jia can visit.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003ccode\u003efindMaxAttraction(n, start, d, attraction)\u003c/code\u003e\u003cul\u003e\n\u003cli\u003e\u003ccode\u003en\u003c/code\u003e: the number of cities.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003estart\u003c/code\u003e: the index of the starting city.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003ed\u003c/code\u003e: the number of days.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eattraction\u003c/code\u003e: array of length \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e; \u003ccode\u003eattraction[i]\u003c/code\u003e is the number of attractions in city \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e, for \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/9ccfdb653fe0394798975b5c4902b9a5?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:13.56ex; height:2.343ex;\" alt\u003d\"0 \\le i \\le n-1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i \\le n-1~\u003c/span\u003e\u003c/span\u003e.\u003c/li\u003e\n\u003cli\u003eThe function should return the maximum number of attractions Jian-Jia can visit.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch4\u003eSubtasks\u003c/h4\u003e\n\u003cp\u003eIn all subtasks \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/922118b795277b9eaf8486f2ea5e2800?v\u003d1715004944\" style\u003d\"vertical-align: -0.838ex; width:19.757ex; height:2.843ex;\" alt\u003d\"0 \\le d \\le 2n+\\lfloor n/2\\rfloor\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le d \\le 2n+\\lfloor n/2\\rfloor~\u003c/span\u003e\u003c/span\u003e, and the number of attractions in each city is non-negative.\u003c/p\u003e\n\u003ch5\u003eAdditional constraints:\u003c/h5\u003e\n\u003ctable class\u003d\"table\"\u003e\n\u003ctbody\u003e\u003ctr\u003e\u003cth\u003esubtask\u003c/th\u003e\u003cth\u003epoints\u003c/th\u003e\u003cth\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e\u003c/th\u003e\u003cth\u003emaximum number of attractions in a city\u003c/th\u003e\u003cth\u003estarting city\u003c/th\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e7\u003c/td\u003e\u003ctd\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/77c5104c1da6f8ecba7245c064702b18?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:11.079ex; height:2.343ex;\" alt\u003d\"2 \\le n \\le 20\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2 \\le n \\le 20~\u003c/span\u003e\u003c/span\u003e\u003c/td\u003e\u003ctd\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/98f09d5d02dad6def63669d08840bd5a?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:12.786ex; height:2.176ex;\" alt\u003d\"1\\,000\\,000\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1\\,000\\,000\\,000~\u003c/span\u003e\u003c/span\u003e\u003c/td\u003e\u003ctd\u003eno constraints\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003e23\u003c/td\u003e\u003ctd\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0e06ca6bf3e62138178bd30ec2030515?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:16.116ex; height:2.343ex;\" alt\u003d\"2 \\le n \\le 100\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2 \\le n \\le 100\\,000~\u003c/span\u003e\u003c/span\u003e\u003c/td\u003e\u003ctd\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/95d030779dddad55d98b7269350f5da9?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:3.487ex; height:2.176ex;\" alt\u003d\"100\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~100~\u003c/span\u003e\u003c/span\u003e\u003c/td\u003e\u003ctd\u003ecity 0\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003e17\u003c/td\u003e\u003ctd\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/bacf909075ae1e69eeff61758e080420?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:13.791ex; height:2.343ex;\" alt\u003d\"2 \\le n \\le 3\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2 \\le n \\le 3\\,000~\u003c/span\u003e\u003c/span\u003e\u003c/td\u003e\u003ctd\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/98f09d5d02dad6def63669d08840bd5a?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:12.786ex; height:2.176ex;\" alt\u003d\"1\\,000\\,000\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1\\,000\\,000\\,000~\u003c/span\u003e\u003c/span\u003e\u003c/td\u003e\u003ctd\u003eno constraints\u003c/td\u003e\u003c/tr\u003e\n\u003ctr\u003e\u003ctd\u003e4\u003c/td\u003e\u003ctd\u003e53\u003c/td\u003e\u003ctd\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0e06ca6bf3e62138178bd30ec2030515?v\u003d1715004944\" style\u003d\"vertical-align: -0.505ex; width:16.116ex; height:2.343ex;\" alt\u003d\"2 \\le n \\le 100\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2 \\le n \\le 100\\,000~\u003c/span\u003e\u003c/span\u003e\u003c/td\u003e\u003ctd\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/98f09d5d02dad6def63669d08840bd5a?v\u003d1715004944\" style\u003d\"vertical-align: -0.338ex; width:12.786ex; height:2.176ex;\" alt\u003d\"1\\,000\\,000\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1\\,000\\,000\\,000~\u003c/span\u003e\u003c/span\u003e\u003c/td\u003e\u003ctd\u003eno constraints\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003ch4\u003eImplementation details\u003c/h4\u003e\n\u003cp\u003eYour submission should implement the subprogram described above using the following signatures.\u003c/p\u003e\n\u003cp\u003eNote that the result may be large, and the return type of \u003ccode\u003efindMaxAttraction\u003c/code\u003e is a 64-bit integer.\u003c/p\u003e\n\u003ch5\u003eC/C++ program\u003c/h5\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"kt\"\u003elong\u003c/span\u003e \u003cspan class\u003d\"kt\"\u003elong\u003c/span\u003e \u003cspan class\u003d\"kt\"\u003eint\u003c/span\u003e \u003cspan class\u003d\"nf\"\u003efindMaxAttraction\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e(\u003c/span\u003e\u003cspan class\u003d\"kt\"\u003eint\u003c/span\u003e \u003cspan class\u003d\"n\"\u003en\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"kt\"\u003eint\u003c/span\u003e \u003cspan class\u003d\"n\"\u003estart\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"kt\"\u003eint\u003c/span\u003e \u003cspan class\u003d\"n\"\u003ed\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"kt\"\u003eint\u003c/span\u003e \u003cspan class\u003d\"n\"\u003eattraction\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e[]);\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003ch5\u003ePascal program\u003c/h5\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"k\"\u003efunction\u003c/span\u003e \u003cspan class\u003d\"nf\"\u003efindMaxAttraction\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e(\u003c/span\u003e\u003cspan class\u003d\"n\"\u003en\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"n\"\u003estart\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"n\"\u003ed\u003c/span\u003e \u003cspan class\u003d\"o\"\u003e:\u003c/span\u003e \u003cspan class\u003d\"kt\"\u003elongint\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e;\u003c/span\u003e \u003cspan class\u003d\"n\"\u003eattraction\u003c/span\u003e \u003cspan class\u003d\"o\"\u003e:\u003c/span\u003e \u003cspan class\u003d\"k\"\u003earray\u003c/span\u003e \u003cspan class\u003d\"k\"\u003eof\u003c/span\u003e \u003cspan class\u003d\"kt\"\u003elongint\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e)\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e:\u003c/span\u003e \u003cspan class\u003d\"kt\"\u003eint64\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e;\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003c/div\u003e\n\u003chr\u003e\n\n\u003c/div\u003e"}}]}