Submission #00037
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | #include <bits/stdc++.h> #define INF 1<<29 using namespace std; int n,d; int p[111][111]; int minp[111]; int dp[111][111]; int path[111][111]; int main() { cin >> n >> d; for ( int i=0;i<n;i++) { for ( int j=0;j<d;j++) { cin >> p[i][j]; } } int sum = 0; for ( int j=0;j<d;j++) { minp[j] = INF; for ( int i=0;i<n;i++) { if (minp[j] > p[i][j]) { minp[j] = p[i][j]; } path[i][j] = 100; } sum+=minp[j]; } int count_min[100]; memset (count_min, 100, sizeof (count_min)); for ( int i = 0; i < n; i++) { if (minp[d-1] == p[i][d-1]){ dp[i][d-1] = 0; } else { dp[i][d-1] = 100; } for ( int j=0;j<d-1;j++) { dp[i][j] = 100; } } count_min[d-1] = 0; int k; for ( int j=d-2;j>=0;j--) { for ( int i=0;i<n;i++) { if (minp[j] != p[i][j]) continue ; if (dp[i][j+1] == count_min[j+1]) { dp[i][j] = count_min[j+1]; path[i][j] = min(i, path[i][j]); } else { dp[i][j] = count_min[j+1] + 1; if (dp[i][j] == dp[i][j+1]) { path[i][j] = min(i, path[i][j]); } for ( int k=0;k<n;k++){ if (dp[k][j+1] == count_min[j+1]) { path[i][j] = min(k, path[i][j]); break ; } } } count_min[j] = min(count_min[j], dp[i][j]); } } int ans[50]; int prev = -1; int temp; for ( int i=n-1;i>=0;i--) { if (count_min[0] == dp[i][0]) { ans[0] = i; } } for ( int j=0;j<d;j++) { ans[j+1] = path[ans[j]][j]; } cout << sum << " " << count_min[0] << endl; for ( int j=0;j<d;j++) { cout << ans[j] + 1 << endl; } } |
ステータス
項目 | データ |
---|---|
問題 | 0005 - ホテル探し |
ユーザー名 | udonkun |
投稿日時 | 2016-08-12 09:58:57 |
言語 | C++11 |
状態 | Accepted |
得点 | 11 |
ソースコード長 | 1648 Byte |
最大実行時間 | 17 ms |
最大メモリ使用量 | 808 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 11 / 11 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
2517-in1.txt | AC | 14 ms | 476 KB |
1
|
2517-in2.txt | AC | 10 ms | 532 KB |
1
|
2517-in3.txt | AC | 10 ms | 596 KB |
1
|
2517-in4.txt | AC | 12 ms | 676 KB |
1
|
2517-in5.txt | AC | 13 ms | 708 KB |
1
|
2517-in6.txt | AC | 14 ms | 752 KB |
1
|
2517-in7.txt | AC | 13 ms | 652 KB |
1
|
2517-in8.txt | AC | 10 ms | 744 KB |
1
|
2517-in9.txt | AC | 10 ms | 788 KB |
1
|
2517-in10.txt | AC | 17 ms | 440 KB |
1
|
2517-in11.txt | AC | 11 ms | 500 KB |
1
|
2517-in12.txt | AC | 11 ms | 416 KB |
1
|
2517-in13.txt | AC | 11 ms | 484 KB |
1
|
2517-in14.txt | AC | 11 ms | 416 KB |
1
|
2517-in15.txt | AC | 13 ms | 492 KB |
1
|
2517-in16.txt | AC | 12 ms | 540 KB |
1
|
2517-in17.txt | AC | 11 ms | 452 KB |
1
|
2517-in18.txt | AC | 11 ms | 524 KB |
1
|
2517-in19.txt | AC | 14 ms | 448 KB |
1
|
2517-in20.txt | AC | 13 ms | 624 KB |
1
|
2517-in21.txt | AC | 13 ms | 696 KB |
1
|
2517-in22.txt | AC | 10 ms | 728 KB |
1
|
2517-in23.txt | AC | 12 ms | 656 KB |
1
|
2517-in24.txt | AC | 14 ms | 684 KB |
1
|
2517-in25.txt | AC | 13 ms | 712 KB |
1
|
2517-in26.txt | AC | 13 ms | 744 KB |
1
|
2517-in27.txt | AC | 14 ms | 768 KB |
1
|
2517-in28.txt | AC | 12 ms | 668 KB |
1
|
2517-in29.txt | AC | 15 ms | 568 KB |
1
|
2517-in30.txt | AC | 15 ms | 500 KB |
1
|
2517-in31.txt | AC | 13 ms | 528 KB |
1
|
2517-in32.txt | AC | 11 ms | 556 KB |
1
|
2517-in33.txt | AC | 13 ms | 588 KB |
1
|
2517-in34.txt | AC | 11 ms | 428 KB |
1
|
2517-in35.txt | AC | 13 ms | 656 KB |
1
|
2517-in36.txt | AC | 14 ms | 688 KB |
1
|
2517-in37.txt | AC | 14 ms | 716 KB |
1
|
2517-in38.txt | AC | 14 ms | 748 KB |
1
|
2517-in39.txt | AC | 15 ms | 780 KB |
1
|
2517-in40.txt | AC | 10 ms | 644 KB |
1
|
2517-in41.txt | AC | 12 ms | 808 KB |
1
|