제출 #585019

#제출 시각아이디문제언어결과실행 시간메모리
585019Mazaalai휴가 (IOI14_holiday)C++17
24 / 100
573 ms65536 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); 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); 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]); } for (int i = 0; i <= st; i++) for (int j = 0; j <= d; j++) { if (d-j-st+i >= 0){ // if (dp[0][i][j] + dp1[1][d-j-st+i] == 72) { // cout << "00 " << i << " " << j << "\n"; // cout << "01 " << d-j-st+i << "\n"; // cout << "02 " << dp[0][i][j] << ' ' << dp1[1][d-j-st+i] << "\n"; // } ans = max(ans, dp[0][i][j] + dp1[1][min(D, d-j-st+i)]); } } for (int i = st; i < n; i++) for (int j = 0; j <= d; j++) { if (d-j-i+st >= 0) { // if (dp[1][i][j] + dp1[0][d-j-i+st] == 72) { // cout << "10 " << i << " " << j << "\n"; // cout << "11 " << d-j-i+st<< "\n"; // cout << "12 " << dp[1][i][j] << ' ' << dp1[0][d-j-i+st] << "\n"; // } 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...