Submission #1695970
Source Code Expand
import java.util.*; public class Main { // private static final String ex = "5\n" + // "0 21 18 11 28\n" + // "21 0 13 10 26\n" + // "18 13 0 23 13\n" + // "11 10 23 0 17\n" + // "28 26 13 17 0"; // private static final String ex = "3\n" + // "0 1 3\n" + // "1 0 2\n" + // "3 2 0"; private static final String ex = "3\n" + "0 1 3\n" + "1 0 1\n" + "3 1 0"; // private static final String ex = "3\n" + // "0 1000000000 1000000000\n" + // "1000000000 0 1000000000\n" + // "1000000000 1000000000 0"; public static void main(String[] args) { System.out.println(solve(new Scanner(System.in))); // System.out.println(solve(new Scanner(ex))); } private static long solve(Scanner scanner) { int N = Integer.parseInt(scanner.nextLine()); long[][] graph = new long[N][N]; for (int i = 0; i < N; i ++) { String[] split = scanner.nextLine().split(" "); for (int j = 0; j < N; j ++) { graph[i][j] = Long.parseLong(split[j]); } } long result = 0; for (int i = 0; i < N; i ++) { for (int j = 0; j < N; j ++) { Set<Long> set = new HashSet<>(); long minI = Long.MAX_VALUE; for (int k = 0; k < N; k ++) { if (i == k) continue; set.add(graph[i][k]); minI = Math.min(minI, graph[i][k]); } long minJ = Long.MAX_VALUE; boolean flag = false; for (int k = 0; k < N; k ++) { if (j == k) continue; if (set.contains(graph[i][j] - graph[k][j])) { flag = true; } minJ = Math.min(minJ, graph[k][j]); } if (minI + minJ > graph[i][j]) { result += graph[i][j]; } else if (!flag) return -1; } } return result / 2; } }
Submission Info
Submission Time | |
---|---|
Task | D - Restoring Road Network |
User | g_votte |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 2208 Byte |
Status | WA |
Exec Time | 443 ms |
Memory | 61212 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | WA | 318 ms | 39996 KB |
02.txt | WA | 255 ms | 43468 KB |
03.txt | WA | 443 ms | 61212 KB |
04.txt | WA | 394 ms | 47052 KB |
05.txt | WA | 281 ms | 43576 KB |
06.txt | WA | 336 ms | 45080 KB |
07.txt | AC | 326 ms | 42772 KB |
08.txt | WA | 238 ms | 41460 KB |
09.txt | WA | 243 ms | 39068 KB |
10.txt | AC | 316 ms | 43088 KB |
11.txt | AC | 297 ms | 43604 KB |
12.txt | AC | 261 ms | 44956 KB |
13.txt | AC | 91 ms | 20948 KB |
subtask0_0.txt | AC | 90 ms | 18764 KB |
subtask0_1.txt | AC | 90 ms | 21844 KB |
subtask0_2.txt | AC | 94 ms | 19668 KB |
subtask0_3.txt | AC | 91 ms | 18900 KB |