Submission #611123

#TimeUsernameProblemLanguageResultExecution timeMemory
611123talant117408Homecoming (BOI18_homecoming)C++17
0 / 100
1018 ms41028 KiB
#include "homecoming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' #define PI 2*acos(0.0) ll solve(int n, int k, int *a, int *b) { vector <ll> prize(n + 1), books(n * 2 + 1), profit(n + 1), pref(n * 2 + 1), dp(n + 1); for (int i = 1; i <= n; i++) { prize[i] = a[i - 1]; books[i] = books[i + n] = b[i - 1]; } for (int i = 1; i <= n * 2; i++) { pref[i] = books[i] + pref[i - 1]; } for (int i = 1; i <= n; i++) { profit[i] = prize[i] - pref[i + k - 1] + pref[i - 1]; } for (int i = 1; i <= n; i++) { dp[i] = max(dp[i - 1], profit[i]); for (int j = i - 1; j; j--) { if (i - j >= k) { dp[i] = max(dp[i], dp[j] + profit[i]); } else { dp[i] = max(dp[i], dp[j] + profit[i] - (pref[j + k - 1] - pref[i - 1])); } } } return dp[n]; } //~ void solve(int test) { //~ } //~ int main() { //~ do_not_disturb //~ int t = 1; //~ cin >> t; //~ for (int i = 1; i <= t; i++) { //~ solve(i); //~ } //~ return 0; //~ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...