Submission #63531

#TimeUsernameProblemLanguageResultExecution timeMemory
63531Just_Solve_The_ProblemHomecoming (BOI18_homecoming)C++11
0 / 100
1086 ms12528 KiB
#include "homecoming.h" #include <bits/stdc++.h> using namespace std; #define ll long long const int N = (int)2e6 + 7; ll pref[N], dp[N]; ll get(int l, int r) { if (!l) return pref[r]; return pref[r] - pref[l - 1]; } ll solve(int n, int k, int a[], int b[]) { for (int i = 0; i < n + n - 2; i++) { pref[i] = ((i != 0) ? pref[i - 1] : 0) + b[i % n]; } ll cost; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { cost = -get(max(j + k - 1, i), i + k - 1) + a[i]; dp[i] = max(dp[i], dp[j] + cost); } dp[i] = max(dp[i], -get(i, i + k - 1) + a[i]); } for (int i = 1; i < n; i++) { dp[i] = max(dp[i], dp[i - 1]); } return dp[n - 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...