Universal Cup Judging System

Universal Cup

実行時間制限: 1.5 s メモリ制限: 512 MB 満点: 100
統計

Du får gitt $n$ tripler av heltall $(a_i, b_i, c_i)$, slik at $a_i < b_i < c_i$. Du må velge et par av verdier fra hver trippel og dermed danne $n$ intervaller. Du må velge parene slik at enhver to forskjellige intervaller har snittlengde lik null. Finn den maksimalt mulige summen av lengdene til intervallene, eller oppgi at det er umulig å velge intervaller som oppfyller betingelsen.

Inndata

Den første linjen inneholder ett heltall $n$ — antallet tripler. De neste $n$ linjene inneholder tre heltall $a_i$, $b_i$ og $c_i$ — den $i$-te trippelen.

Utdata

Hvis det er umulig å danne intervaller som oppfyller betingelsen, skriv ut -1. Ellers, skriv ut den maksimalt mulige summen av lengdene til intervallene.

Begrensninger

$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.

Eksempler

Inndata 1

4
1 2 3
2 3 5
7 8 9
4 7 8

Utdata 1

7

Inndata 2

3
1 2 4
1 2 4
1 2 4

Utdata 2

-1

Merk

I det første eksempelet er det $n = 4$ tripler: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ og $(4, 7, 8)$. Én optimal løsning er: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Disse intervallene oppfyller betingelsen om at enhver to forskjellige intervaller har snittlengde null. Summen av lengdene deres er $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. I det andre eksempelet er det umulig å velge intervallene slik at betingelsen er oppfylt.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.