Submission #240109

#TimeUsernameProblemLanguageResultExecution timeMemory
240109MrRobot_28Go (COCI18_go)C++17
100 / 100
422 ms156920 KiB
#include <bits/stdc++.h> using namespace std; bool cmp(pair <pair <int, int>, int> a, pair <pair <int, int>, int> b) { return a.second < b.second; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k, m; cin >> n >> k >> m; vector <pair <pair <int, int>, int> > mass(m); int ind1 = 0, ind2 = -1; for(int i = 0; i < m; i++) { cin >> mass[i].first.first >> mass[i].first.second >> mass[i].second; mass[i].second--; if(mass[i].first.first <= k) { ind1 = i; } if(mass[i].first.first >= k && ind2 == -1) { ind2 = i; } } int dp[m][m][2000][2]; for(int i = 0; i < m; i++) { for(int j = 0; j < m; j++) { for(int t= 0; t < 2000; t++) { dp[i][j][t][0] = dp[i][j][t][1] = -1e9; } } } int ans = 0; for(int t = 0; t < 2000; t++) { for(int len = 1; len <= m; len++) { for(int i = 0; i <= m - len; i++) { if(len == 1) { if(abs(mass[i].first.first - k) <= mass[i].second) { dp[i][i + len - 1][abs(mass[i].first.first - k)][0] = mass[i].first.second; dp[i][i + len - 1][abs(mass[i].first.first - k)][1] = mass[i].first.second; } else { dp[i][i + len - 1][abs(mass[i].first.first - k)][0] = 0; dp[i][i + len - 1][abs(mass[i].first.first - k)][1] = 0; } } else { if(t >= abs(mass[i].first.first - mass[i + len - 1].first.first)) { dp[i][i + len - 1][t][0] = max(dp[i][i + len - 1][t][0], dp[i + 1][i + len - 1][t - abs(mass[i].first.first - mass[i + len - 1].first.first)][1]); dp[i][i + len - 1][t][1] = max(dp[i][i + len - 1][t][1], dp[i][i + len - 2][t - abs(mass[i].first.first - mass[i + len - 1].first.first)][0]); } if(t >= abs(mass[i].first.first - mass[i + 1].first.first)) { dp[i][i + len - 1][t][0] = max(dp[i][i + len - 1][t][0], dp[i + 1][i + len - 1][t - abs(mass[i].first.first - mass[i + 1].first.first)][0]); } if(t >= abs(mass[i + len - 2].first.first - mass[i + len - 1].first.first)) { dp[i][i + len - 1][t][1] = max(dp[i][i + len - 1][t][1], dp[i][i + len - 2][t - abs(mass[i + len - 2].first.first - mass[i + len - 1].first.first)][1]); } if(t <= mass[i].second) { dp[i][i + len - 1][t][0] += mass[i].first.second; } if(t <= mass[i + len - 1].second) { dp[i][i + len - 1][t][1] += mass[i + len - 1].first.second; } } ans = max(ans, dp[i][i + len - 1][t][0]); ans = max(ans, dp[i][i + len - 1][t][1]); } } } cout << ans; return 0; }

Compilation message (stderr)

go.cpp: In function 'int main()':
go.cpp:15:6: warning: variable 'ind1' set but not used [-Wunused-but-set-variable]
  int ind1 = 0, ind2 = -1;
      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...