Submission #1275376
Source Code Expand
#include <cstdio> #include <vector> #include <algorithm> #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i)) #define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) using namespace std; template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); } template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); } template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); } template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); } int main() { // input int n, s; scanf("%d%d", &n, &s); -- s; vector<int> l(n), r(n); repeat (i,n) scanf("%d%d", &l[i], &r[i]); auto w = vectors(n, n, int()); repeat (i,n) repeat (j,n) scanf("%d", &w[i][j]); // compute // // Warshall Floyd repeat (k,n) { repeat (i,n) { repeat (j,n) { setmin(w[i][j], w[i][k] + w[k][j]); } } } // // dp vector<int> dp(n); repeat (i,n) { if (w[s][i] <= r[i]) { dp[i] = r[i] - max(l[i], w[s][i]); } } repeat (k,n*3+300) { repeat (i,n) { repeat (j,n) { if (r[i] + w[i][j] <= r[j]) { setmax(dp[j], dp[i] + r[j] - max(l[j], r[i] + w[i][j])); } } } } // output int result = *whole(max_element, dp); printf("%d\n", result); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - 7歳教 |
User | kimiyuki |
Language | C++14 (Clang 3.8.0) |
Score | 50 |
Code Size | 1617 Byte |
Status | WA |
Exec Time | 1590 ms |
Memory | 1280 KB |
Judge Result
Set Name | subtask_1 | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 0 / 400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
subtask_1 | 0_00_sample_00.txt, 0_40_Small_DisjointRange_00_0010.txt, 0_40_Small_DisjointRange_04_0500.txt, 0_40_Small_DisjointRange_07_0030.txt, 0_40_Small_DisjointRange_08_0448.txt, 0_40_Small_DisjointRange_13_0121.txt, 0_40_Small_DisjointRange_14_0500.txt, 0_40_Small_DisjointRange_15_0010.txt, 0_40_Small_DisjointRange_16_0002.txt, 0_40_Small_DisjointRange_22_0081.txt, 0_40_Small_OverlapRange_01_0001.txt, 0_40_Small_OverlapRange_02_0061.txt, 0_40_Small_OverlapRange_09_0500.txt, 0_40_Small_OverlapRange_10_0010.txt, 0_40_Small_OverlapRange_11_0013.txt, 0_40_Small_OverlapRange_12_0043.txt, 0_40_Small_OverlapRange_17_0052.txt, 0_40_Small_OverlapRange_21_0016.txt, 0_40_Small_OverlapRange_24_0500.txt, 0_40_Small_RandomRange_03_0117.txt, 0_40_Small_RandomRange_05_0006.txt, 0_40_Small_RandomRange_06_0020.txt, 0_40_Small_RandomRange_18_0123.txt, 0_40_Small_RandomRange_19_0500.txt, 0_40_Small_RandomRange_20_0005.txt, 0_40_Small_RandomRange_23_0148.txt |
All | 0_00_sample_00.txt, 0_40_Small_DisjointRange_00_0010.txt, 0_40_Small_DisjointRange_04_0500.txt, 0_40_Small_DisjointRange_07_0030.txt, 0_40_Small_DisjointRange_08_0448.txt, 0_40_Small_DisjointRange_13_0121.txt, 0_40_Small_DisjointRange_14_0500.txt, 0_40_Small_DisjointRange_15_0010.txt, 0_40_Small_DisjointRange_16_0002.txt, 0_40_Small_DisjointRange_22_0081.txt, 0_40_Small_OverlapRange_01_0001.txt, 0_40_Small_OverlapRange_02_0061.txt, 0_40_Small_OverlapRange_09_0500.txt, 0_40_Small_OverlapRange_10_0010.txt, 0_40_Small_OverlapRange_11_0013.txt, 0_40_Small_OverlapRange_12_0043.txt, 0_40_Small_OverlapRange_17_0052.txt, 0_40_Small_OverlapRange_21_0016.txt, 0_40_Small_OverlapRange_24_0500.txt, 0_40_Small_RandomRange_03_0117.txt, 0_40_Small_RandomRange_05_0006.txt, 0_40_Small_RandomRange_06_0020.txt, 0_40_Small_RandomRange_18_0123.txt, 0_40_Small_RandomRange_19_0500.txt, 0_40_Small_RandomRange_20_0005.txt, 0_40_Small_RandomRange_23_0148.txt, 1_00_sample_01.txt, 1_00_sample_02.txt, 1_10_Random_00_0005.txt, 1_10_Random_01_0010.txt, 1_10_Random_02_0039.txt, 1_10_Random_03_0070.txt, 1_10_Random_04_0450.txt, 1_10_Random_05_0004.txt, 1_10_Random_06_0009.txt, 1_10_Random_07_0037.txt, 1_10_Random_08_0027.txt, 1_10_Random_09_0205.txt, 1_10_Random_10_0010.txt, 1_10_Random_11_0017.txt, 1_10_Random_12_0036.txt, 1_10_Random_13_0087.txt, 1_10_Random_14_0248.txt, 1_10_Random_15_0007.txt, 1_10_Random_16_0008.txt, 1_10_Random_17_0019.txt, 1_10_Random_18_0091.txt, 1_10_Random_19_0353.txt, 1_10_Random_20_0007.txt, 1_10_Random_21_0007.txt, 1_10_Random_22_0015.txt, 1_10_Random_23_0012.txt, 1_10_Random_24_0359.txt, 1_20_BinaryTree_DisjointRange_23_0500.txt, 1_20_BinaryTree_DisjointRange_37_0063.txt, 1_20_BinaryTree_OverlapRange_22_0458.txt, 1_20_BinaryTree_RandomRange_29_0090.txt, 1_20_Complete_OverlapRange_05_0064.txt, 1_20_Complete_OverlapRange_13_0049.txt, 1_20_Complete_OverlapRange_18_0220.txt, 1_20_Complete_RandomRange_14_0223.txt, 1_20_Complete_RandomRange_30_0494.txt, 1_20_ConnectedRandom_DisjointRange_10_0163.txt, 1_20_ConnectedRandom_OverlapRange_21_0028.txt, 1_20_Line_OverlapRange_36_0006.txt, 1_20_NoEdge_OverlapRange_03_0500.txt, 1_20_NoEdge_OverlapRange_06_0289.txt, 1_20_NoEdge_OverlapRange_12_0007.txt, 1_20_NoEdge_OverlapRange_15_0500.txt, 1_20_NoEdge_OverlapRange_27_0500.txt, 1_20_NoEdge_OverlapRange_35_0500.txt, 1_20_RandomTree_DisjointRange_04_0005.txt, 1_20_RandomTree_DisjointRange_34_0331.txt, 1_20_RandomTree_OverlapRange_07_0500.txt, 1_20_RandomTree_OverlapRange_32_0003.txt, 1_20_RandomTree_RandomRange_17_0081.txt, 1_20_Random_DisjointRange_20_0010.txt, 1_20_Random_RandomRange_33_0010.txt, 1_20_Ring_DisjointRange_02_0497.txt, 1_20_Ring_DisjointRange_11_0500.txt, 1_20_Ring_DisjointRange_16_0007.txt, 1_20_Ring_DisjointRange_31_0500.txt, 1_20_Ring_DisjointRange_39_0500.txt, 1_20_Ring_OverlapRange_01_0042.txt, 1_20_Ring_OverlapRange_09_0017.txt, 1_20_Ring_OverlapRange_25_0015.txt, 1_20_Ring_OverlapRange_26_0314.txt, 1_20_Ring_OverlapRange_38_0311.txt, 1_20_Star_DisjointRange_00_0009.txt, 1_20_Star_OverlapRange_08_0005.txt, 1_20_Star_OverlapRange_28_0003.txt, 1_20_Star_RandomRange_19_0500.txt, 1_20_Star_RandomRange_24_0003.txt, 1_30_DisConnected_DisjointRange_04_0062.txt, 1_30_DisConnected_OverlapRange_02_0451.txt, 1_30_DisConnected_OverlapRange_05_0172.txt, 1_30_DisConnected_OverlapRange_08_0105.txt, 1_30_DisConnected_RandomRange_00_0010.txt, 1_30_DisConnected_RandomRange_01_0097.txt, 1_30_DisConnected_RandomRange_03_0010.txt, 1_30_DisConnected_RandomRange_06_0010.txt, 1_30_DisConnected_RandomRange_07_0095.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00_sample_00.txt | AC | 1 ms | 256 KB |
0_40_Small_DisjointRange_00_0010.txt | AC | 1 ms | 256 KB |
0_40_Small_DisjointRange_04_0500.txt | AC | 1453 ms | 1280 KB |
0_40_Small_DisjointRange_07_0030.txt | AC | 2 ms | 256 KB |
0_40_Small_DisjointRange_08_0448.txt | AC | 1030 ms | 1024 KB |
0_40_Small_DisjointRange_13_0121.txt | AC | 25 ms | 256 KB |
0_40_Small_DisjointRange_14_0500.txt | AC | 1472 ms | 1280 KB |
0_40_Small_DisjointRange_15_0010.txt | AC | 1 ms | 256 KB |
0_40_Small_DisjointRange_16_0002.txt | AC | 1 ms | 256 KB |
0_40_Small_DisjointRange_22_0081.txt | AC | 9 ms | 256 KB |
0_40_Small_OverlapRange_01_0001.txt | AC | 1 ms | 256 KB |
0_40_Small_OverlapRange_02_0061.txt | AC | 5 ms | 256 KB |
0_40_Small_OverlapRange_09_0500.txt | AC | 1454 ms | 1280 KB |
0_40_Small_OverlapRange_10_0010.txt | AC | 1 ms | 256 KB |
0_40_Small_OverlapRange_11_0013.txt | AC | 1 ms | 256 KB |
0_40_Small_OverlapRange_12_0043.txt | AC | 3 ms | 256 KB |
0_40_Small_OverlapRange_17_0052.txt | AC | 4 ms | 256 KB |
0_40_Small_OverlapRange_21_0016.txt | AC | 1 ms | 256 KB |
0_40_Small_OverlapRange_24_0500.txt | AC | 1486 ms | 1280 KB |
0_40_Small_RandomRange_03_0117.txt | AC | 23 ms | 256 KB |
0_40_Small_RandomRange_05_0006.txt | AC | 1 ms | 256 KB |
0_40_Small_RandomRange_06_0020.txt | AC | 2 ms | 256 KB |
0_40_Small_RandomRange_18_0123.txt | AC | 26 ms | 384 KB |
0_40_Small_RandomRange_19_0500.txt | AC | 1480 ms | 1280 KB |
0_40_Small_RandomRange_20_0005.txt | AC | 1 ms | 256 KB |
0_40_Small_RandomRange_23_0148.txt | AC | 42 ms | 384 KB |
1_00_sample_01.txt | AC | 1 ms | 256 KB |
1_00_sample_02.txt | AC | 1 ms | 256 KB |
1_10_Random_00_0005.txt | AC | 1 ms | 256 KB |
1_10_Random_01_0010.txt | AC | 1 ms | 256 KB |
1_10_Random_02_0039.txt | AC | 2 ms | 256 KB |
1_10_Random_03_0070.txt | AC | 7 ms | 256 KB |
1_10_Random_04_0450.txt | AC | 1059 ms | 1024 KB |
1_10_Random_05_0004.txt | AC | 1 ms | 256 KB |
1_10_Random_06_0009.txt | AC | 1 ms | 256 KB |
1_10_Random_07_0037.txt | AC | 2 ms | 256 KB |
1_10_Random_08_0027.txt | AC | 2 ms | 256 KB |
1_10_Random_09_0205.txt | AC | 86 ms | 384 KB |
1_10_Random_10_0010.txt | AC | 1 ms | 256 KB |
1_10_Random_11_0017.txt | AC | 1 ms | 256 KB |
1_10_Random_12_0036.txt | AC | 2 ms | 256 KB |
1_10_Random_13_0087.txt | AC | 11 ms | 256 KB |
1_10_Random_14_0248.txt | AC | 178 ms | 512 KB |
1_10_Random_15_0007.txt | AC | 1 ms | 256 KB |
1_10_Random_16_0008.txt | AC | 1 ms | 256 KB |
1_10_Random_17_0019.txt | AC | 1 ms | 256 KB |
1_10_Random_18_0091.txt | AC | 13 ms | 256 KB |
1_10_Random_19_0353.txt | AC | 514 ms | 768 KB |
1_10_Random_20_0007.txt | AC | 1 ms | 256 KB |
1_10_Random_21_0007.txt | AC | 1 ms | 256 KB |
1_10_Random_22_0015.txt | AC | 1 ms | 256 KB |
1_10_Random_23_0012.txt | AC | 1 ms | 256 KB |
1_10_Random_24_0359.txt | AC | 530 ms | 768 KB |
1_20_BinaryTree_DisjointRange_23_0500.txt | AC | 1490 ms | 1280 KB |
1_20_BinaryTree_DisjointRange_37_0063.txt | AC | 5 ms | 256 KB |
1_20_BinaryTree_OverlapRange_22_0458.txt | AC | 1120 ms | 1152 KB |
1_20_BinaryTree_RandomRange_29_0090.txt | AC | 11 ms | 256 KB |
1_20_Complete_OverlapRange_05_0064.txt | AC | 6 ms | 256 KB |
1_20_Complete_OverlapRange_13_0049.txt | AC | 3 ms | 256 KB |
1_20_Complete_OverlapRange_18_0220.txt | AC | 132 ms | 512 KB |
1_20_Complete_RandomRange_14_0223.txt | AC | 134 ms | 512 KB |
1_20_Complete_RandomRange_30_0494.txt | AC | 1436 ms | 1280 KB |
1_20_ConnectedRandom_DisjointRange_10_0163.txt | AC | 55 ms | 384 KB |
1_20_ConnectedRandom_OverlapRange_21_0028.txt | AC | 2 ms | 256 KB |
1_20_Line_OverlapRange_36_0006.txt | AC | 1 ms | 256 KB |
1_20_NoEdge_OverlapRange_03_0500.txt | AC | 590 ms | 1280 KB |
1_20_NoEdge_OverlapRange_06_0289.txt | AC | 133 ms | 640 KB |
1_20_NoEdge_OverlapRange_12_0007.txt | AC | 1 ms | 256 KB |
1_20_NoEdge_OverlapRange_15_0500.txt | AC | 591 ms | 1280 KB |
1_20_NoEdge_OverlapRange_27_0500.txt | AC | 590 ms | 1280 KB |
1_20_NoEdge_OverlapRange_35_0500.txt | AC | 590 ms | 1280 KB |
1_20_RandomTree_DisjointRange_04_0005.txt | AC | 1 ms | 256 KB |
1_20_RandomTree_DisjointRange_34_0331.txt | AC | 421 ms | 640 KB |
1_20_RandomTree_OverlapRange_07_0500.txt | AC | 1485 ms | 1280 KB |
1_20_RandomTree_OverlapRange_32_0003.txt | AC | 1 ms | 256 KB |
1_20_RandomTree_RandomRange_17_0081.txt | AC | 8 ms | 256 KB |
1_20_Random_DisjointRange_20_0010.txt | AC | 1 ms | 256 KB |
1_20_Random_RandomRange_33_0010.txt | AC | 1 ms | 256 KB |
1_20_Ring_DisjointRange_02_0497.txt | AC | 1563 ms | 1280 KB |
1_20_Ring_DisjointRange_11_0500.txt | WA | 1590 ms | 1280 KB |
1_20_Ring_DisjointRange_16_0007.txt | AC | 1 ms | 256 KB |
1_20_Ring_DisjointRange_31_0500.txt | WA | 1568 ms | 1280 KB |
1_20_Ring_DisjointRange_39_0500.txt | WA | 1582 ms | 1280 KB |
1_20_Ring_OverlapRange_01_0042.txt | WA | 3 ms | 256 KB |
1_20_Ring_OverlapRange_09_0017.txt | AC | 1 ms | 256 KB |
1_20_Ring_OverlapRange_25_0015.txt | WA | 1 ms | 256 KB |
1_20_Ring_OverlapRange_26_0314.txt | AC | 384 ms | 640 KB |
1_20_Ring_OverlapRange_38_0311.txt | WA | 371 ms | 640 KB |
1_20_Star_DisjointRange_00_0009.txt | AC | 1 ms | 256 KB |
1_20_Star_OverlapRange_08_0005.txt | AC | 1 ms | 256 KB |
1_20_Star_OverlapRange_28_0003.txt | AC | 1 ms | 256 KB |
1_20_Star_RandomRange_19_0500.txt | AC | 1516 ms | 1280 KB |
1_20_Star_RandomRange_24_0003.txt | AC | 1 ms | 256 KB |
1_30_DisConnected_DisjointRange_04_0062.txt | WA | 5 ms | 256 KB |
1_30_DisConnected_OverlapRange_02_0451.txt | AC | 1021 ms | 1024 KB |
1_30_DisConnected_OverlapRange_05_0172.txt | AC | 64 ms | 384 KB |
1_30_DisConnected_OverlapRange_08_0105.txt | AC | 16 ms | 256 KB |
1_30_DisConnected_RandomRange_00_0010.txt | AC | 1 ms | 256 KB |
1_30_DisConnected_RandomRange_01_0097.txt | AC | 14 ms | 256 KB |
1_30_DisConnected_RandomRange_03_0010.txt | AC | 1 ms | 256 KB |
1_30_DisConnected_RandomRange_06_0010.txt | AC | 1 ms | 256 KB |
1_30_DisConnected_RandomRange_07_0095.txt | WA | 13 ms | 256 KB |