Submission #585021

#TimeUsernameProblemLanguageResultExecution timeMemory
585021MazaalaiHoliday (IOI14_holiday)C++17
24 / 100
5056 ms48460 KiB
#include <bits/stdc++.h> #include"holiday.h" #define ALL(x) x.begin(),x.end() #define LLA(x) x.rbegin(),x.rend() #define pb push_back using namespace std; using PII = pair <int, int>; using ll = long long; const int N = 3001; const int D = 6000; const int D1 = 7500; ll dp[2][N][D+1]; ll dp1[2][D1+1]; long long int findMaxAttraction(int n, int st, int d, int nums[]) { ll ans = 0; // return 0; { for (int i = st; i >= 0; i--) { multiset <int> vals; ll sum = 0; int a = st - i; for (int j = i; j <= st; j++) { vals.insert(nums[j]); sum += nums[j]; } for (int j = vals.size(); j > 0; j--) { if (a+j <= d) { ans = max(ans, sum); if (n <= N) dp[0][i][a+j] = sum; dp1[0][a+j] = max(dp1[0][a+j], sum); } sum -= *vals.begin(); vals.erase(vals.begin()); } } for (int i = st+1; i < n; i++) { multiset <int> vals; ll sum = 0; int b = i - st; for (int j = st+1; j <= i; j++) { vals.insert(nums[j]); sum += nums[j]; } for (int j = vals.size(); j > 0; j--) { if (j+b <= d) { ans = max(ans, sum); if (n <= N) dp[1][i][j+b] = sum; dp1[1][j+b] = max(dp1[1][j+b], sum); } sum -= *vals.begin(); vals.erase(vals.begin()); } } } for (int i = 1; i <= d; i++) { dp1[0][i]=max(dp1[0][i], dp1[0][i-1]); dp1[1][i]=max(dp1[1][i], dp1[1][i-1]); } if (n <= N) for (int i = 0; i <= st; i++) for (int j = 0; j <= d; j++) { if (d-j-st+i >= 0){ ans = max(ans, dp[0][i][j] + dp1[1][min(D, d-j-st+i)]); } } if (n <= N) for (int i = st; i < n; i++) for (int j = 0; j <= d; j++) { if (d-j-i+st >= 0) { ans = max(ans, dp[1][i][j] + dp1[0][min(D, d-j-i+st)]); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...