35353번 - 神経衰弱 2 (Pair Matching 2) 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 11 | 4 | 4 | 57.143% |
문제
2N 枚のカードが机の上に横一列に並んでおり，左から順に 1, 2, …, 2N の番号が付けられている．カード i (1 ≦ i ≦ 2N) には整数 Ai が書かれている．各 x = 1, 2, …, N について，整数 x が書かれたカードはちょうど 2 枚存在する．
ビーバーのビ太郎は，これらのカードを用いて 神経衰弱 と呼ばれるゲームを行う．ビ太郎は，右手と左手に 1 枚ずつカードを持つことができる． 神経衰弱 は以下の手順で行われる．
- i = 1, 2, …, 2N の順に以下を行う．
- ビ太郎は，カード i を拾うか拾わないかを選ぶ．カードを拾おうとする場合，以下の 2. から 5. が順に起こる．カードを拾わない場合，以下の 2. から 5. はスキップする．
- 整数 Ai が書かれたカードをビ太郎が持っているならば，そのカードと机の上にあるカード i は消滅し，ビ太郎は VAi の点数を得る．
- ビ太郎が左手にカードを持っているならば，そのカードを捨てる．
- ビ太郎が右手にカードを持っているならば，そのカードを左手に移す．
- カード i が存在する（消滅していない）ならば，ビ太郎は右手でカード i を持つ．
これらの手順で得た点数の合計が最終的なビ太郎のスコアとなる．ビ太郎は，このゲームで得ることのできるスコアの最大値を知りたい．
カードの並びと各整数に割り当てられた点数の情報が与えられたとき，ビ太郎が得ることのできるスコアの最大値を求めるプログラムを作成せよ．
입력
入力は以下の形式で与えられる．
N
A1 A2 … A2N
V1 V2 … VN
출력
ビ太郎が得ることのできるスコアの最大値を出力せよ．
제한
- 1 ≦ N ≦ 400 000．
- (A1, A2, …, A2N) は (1, 1, 2, 2, …, N, N) の並べ替えである．
- 1 ≦ Vk ≦ 109 (1 ≦ k ≦ N)．
- 入力される値はすべて整数である．
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | (A1, A2, …, AN) = (1, 2, …, N)，N ≦ 5 000． |
| 2 | 12 | (A1, A2, …, AN) = (1, 2, …, N)． |
| 3 | 6 | N ≦ 9． |
| 4 | 9 | N ≦ 18． |
| 5 | 16 | N ≦ 300． |
| 6 | 18 | N ≦ 3 000． |
| 7 | 18 | N ≦ 150 000，Vk = 1 (1 ≦ k ≦ N)． |
| 8 | 8 | N ≦ 150 000． |
| 9 | 5 | 追加の制約はない． |
예제 입력 1
3 1 2 3 1 2 3 5 2 8
예제 출력 1
13
ビ太郎は以下の手順でスコア 13 を得ることができる．
- カード 1 を拾おうとする．カード 1 には整数 1 が書かれている．ビ太郎は整数 1 が書かれたカードを持っていないから，カードの消滅は起こらない．ビ太郎は右手にカード 1 を持った状態になる．
- カード 2 は拾わずスキップする．
- カード 3 を拾おうとする．カード 3 には整数 3 が書かれている．ビ太郎は整数 3 が書かれたカードを持っていないから，カードの消滅は起こらない．ビ太郎は左手にカード 1 を，右手にカード 3 を持った状態になる．
- カード 4 を拾おうとする．カード 4 には整数 1 が書かれている．ビ太郎は整数 1 の書かれたカード 1 を持っているから，左手に持ったカード 1 と机の上のカード 4 は消滅し，ビ太郎は V1 = 5 の点数を得る．その後，ビ太郎は左手にカード 3 を持った状態になる．
- カード 5 は拾わずスキップする．
- カード 6 を拾おうとする．カード 6 には整数 3 が書かれている．ビ太郎は整数 3 の書かれたカード 3 を持っているから，左手に持ったカード 3 と机の上のカード 6 は消滅し，ビ太郎は V3 = 8 の点数を得る．その後，ビ太郎はどちらの手にもカードを持っていない状態になる．
ビ太郎は 13 より大きいスコアを得ることはできないため，13 を出力する．
この入力例は小課題 1, 2, 3, 4, 5, 6, 8, 9 の制約を満たす．
예제 입력 2
4 1 2 1 2 3 4 4 3 39 62 55 21
예제 출력 2
156
ビ太郎は，例えばカード 1, 2, 3, 4, 5, 6, 8 を拾おうとすることで，スコア V1 + V2 + V3 = 156 を得ることができる．
ビ太郎は 156 より大きいスコアを得ることはできないため，156 を出力する．
この入力例は小課題 3, 4, 5, 6, 8, 9 の制約を満たす．
예제 입력 3
10 7 2 5 8 4 10 8 2 7 5 6 3 4 1 10 9 9 1 6 3 185163245 734376902 849123714 97860221 844860642 689054872 471545587 607735137 664633003 831663829
예제 출력 3
3117416130
この入力例は小課題 4, 5, 6, 8, 9 の制約を満たす．
예제 입력 4
15 4 3 8 3 10 15 14 1 12 4 13 1 6 7 10 15 2 8 12 2 9 11 11 13 5 9 14 5 6 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
예제 출력 4
6
この入力例は小課題 4, 5, 6, 7, 8, 9 の制約を満たす．
출처
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics for Girls > JOIG 2024/2025 5번
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호