Submission #1276208

#TimeUsernameProblemLanguageResultExecution timeMemory
1276208KindaGoodGamesHoliday (IOI14_holiday)C++20
0 / 100
67 ms131072 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; #define int long long int solve(int n, int s, int d, vector<int> arr){ int best = 0; int mar =0; int R[8000][8000]; int bleft[8000]; for(int k = 0; k <= d; k++){ int sum = 0; int ma = 0; priority_queue<int, vector<int>, greater<int>> pq; for(int i = s; i < n; i++){ sum += arr[i]; int len = i-s; pq.push(arr[i]); if(len > k) break; while(len+pq.size() > k){ sum -= pq.top(); pq.pop(); } R[k][len] = sum; mar = max(mar,sum); } } if(s == 0){ return mar; } s--; for(int k = 0; k <= d; k++){ int sum = 0; int ma = 0; priority_queue<int, vector<int>, greater<int>> pq; for(int i = s; i >= 0; i--){ sum += arr[i]; int len = s-i; pq.push(arr[i]); if(len > k) break; while(len+pq.size() > k){ sum -= pq.top(); pq.pop(); } ma = max(ma,sum); } bleft[k] = ma; } int ans = 0; for(int l = 0; l <= d; l++){ for(int steps = 0; steps <= l; steps++){ int r = d-l-steps-1; if(r < 0) break; int c = 0; c += R[l][min(steps,l)]; c += bleft[r]; if(c > ans){ ans = c; } } } return ans; } long long findMaxAttraction(int32_t n, int32_t s, int32_t d, int32_t A[]) { vector<int> arr(n); for(int i = 0; i < n; i++){ arr[i] = A[i]; } int v1 = 0; v1 = solve(n,s,d,arr); reverse(arr.begin(),arr.end()); s = (n-1)-s; int v2 = 0; v2 = solve(n,s,d,arr); return max(v1,v2); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...