20318번 - Carska Civilizacija 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 512 MB | 10 | 1 | 1 | 12.500% |
문제
Nakon apokalipse došlo je vrijeme za uzdizanje nove civilizacije predvođene gospodinom Malnarom. Prvo što će napraviti je obnoviti tramvajsku mrežu u glavnoj ulici svoga carstva.
Određeno je n potencijalnih mjesta uzduž ulice, a gospodin Malnar izabrat će neka od njih na kojima će izgraditi tramvajske postaje. Već je određeno da će se na prvom i n-tom mjestu nalaziti okretišta pa ta mjesta svakako moraju biti odabrana.
Za svako mjesto poznate su vrijednosti xi i ci, gdje xi predstavlja udaljenost tog mjesta od početka ulice, a ci predstavlja nezadovoljstvo stanovnika kada bi postaja bila na tom mjestu. Naime, kod nekih postaja nalaze se kiosci čiji prodavači uvijek podvale skupe karte, a kod nekih odlične pekare.
Postoji ukupno m stanovnika koji će koristiti planiranu liniju pa je gospodin Malnar odlučio pitati svakog od njih za mišljenje. Saznao je da i-ti stanovnik mrzi vožnje duljine di te ocjenjuje izbor postaja na sljedeći način:
- ukupno zadovoljstvo tog stanovnika jednako je zbroju zadovoljstva za svaki par uzastopnih izabranih postaja
- zadovoljstvo sa dvije uzastopne izabrane postaje koje su udaljene za d jednako je |d − di|
Ukupno zadovoljstvo gospodin Malnar računa tako da zbroji zadovoljstva svih m stanovnika te na kraju oduzme nezadovoljstva ck svih postaja k koje su odabrane. Ispišite maksimalno zadovoljstvo koje gospodin Malnar može postići uz optimalan izbor postaja.
입력
U prvom su retku prirodni brojevi n (2 ≤ n ≤ 100 000) i m (1 ≤ m ≤ 100 000) iz teksta zadatka.
Slijedi redak s m cijelih brojeva di (0 ≤ di ≤ 107) iz teksta zadatka.
Slijedi n redaka koji opisuju potencijalne postaje. Svaka postaja opisana je pozicijom xi (0 ≤ xi ≤ 107) i nezadovoljstvom ci (0 ≤ |ci| ≤ 1012). Brojevi xi i ci su cjelobrojni te dodatno vrijedi x1 < x2 < . . . < xn.
출력
U jedinom retku ispišite najveće moguće zadovoljstvo.
예제 입력 1
2 1 10 0 5 20 3
예제 출력 1
2
예제 입력 2
3 3 3 7 10 2 20 5 4 10 -3
예제 출력 2
-1
예제 입력 3
9 5 30 64 2 93 67 0 81 1 256 6 251 13 256 23 180 52 256 72 94 77 256 97 12
예제 출력 3
137
힌트
Pojašnjenje trećeg probnog primjera: Optimalno je izabrati postaje 1, 3, 5, 7 i 9. Uzastopne udaljenosti tada su 6, 17, 49 i 25, a zadovoljstva stanovnika redom 61, 159, 89, 275 i 171. Zbroj njihovih zadovoljstava je 755, a ukupno nezadovoljstvo izbora je 618 pa je konačni rezultat 137.