Submission #366509

#TimeUsernameProblemLanguageResultExecution timeMemory
366509idk321Pinball (JOI14_pinball)C++11
0 / 100
1 ms620 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll M = 1000000000000000000LL; const int N = 205; int main() { ios::sync_with_stdio(0); cin.tie(0); int m, n; cin >> m >> n; vector<array<int, 4>> devices(m); set<int> values; values.insert(1); values.insert(n); for (int i = 0; i < m; i++) { int a, b, c, d; cin >> a >> b >> c >> d; devices[i][0] = a; values.insert(a); devices[i][1] = b; values.insert(b); devices[i][2] = c; devices[i][3] = d; } map<int, int> to; int curTo = 1; for (int i : values) { to[i] = curTo; curTo++; } n = to[n]; for (auto& device : devices) { for (int i = 0; i <= 2; i++) device[i] = to[device[i]]; } ll dp[N][N]; for (int i = 0; i <N; i++) for (int j = 0; j < N; j++) dp[i][j] = M; for (int i = m - 1; i >= 0; i--) { int x = devices[i][0]; int y = devices[i][1]; int c = devices[i][2]; int d = devices[i][3]; dp[x][y] = min<ll>(dp[x][y], d); for (int j = 1; j <= n; j++) { for (int k = j; k <= n; k++) { if (c >= j && c <= k) { dp[min(j, x)][max(k, y)] = min(dp[min(j, x)][max(k, y)], dp[j][k] + d); } } } } if (dp[1][n] == M) cout << -1 << "\n"; else cout << dp[1][n] << "\n"; } /* 5 6 2 4 3 5 1 2 2 8 3 6 5 2 4 6 4 7 2 4 3 10 */ /* 6 6 2 4 3 5 1 2 2 8 3 6 5 2 4 6 4 7 2 4 3 10 1 5 1 4 */ /* 3 5 2 4 3 10 1 3 1 20 2 5 4 30 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...