제출 #763733

#제출 시각아이디문제언어결과실행 시간메모리
763733a_aguilo휴가 (IOI14_holiday)C++14
0 / 100
38 ms65536 KiB
#include<bits/stdc++.h> #include "holiday.h" using namespace std; //vector<int> values; vector<vector<long long int>> dp; int N, D, START; long long solveLeft(int city, int day, int attraction[]){ if(city < 0) return 0; if(day <= 0) return 0; if(dp[city][day] != -1) return dp[city][day]; dp[city][day] = max(solveLeft(city-1, day-1, attraction), solveLeft(city-1, day-2, attraction) + (long long)attraction[city]); return dp[city][day]; } long long solveRight(int city, int day, int attraction[]){ if(city >= N) return 0; if(day <= 0) return 0; if (dp[city][day] != -1) return dp[city][day]; //cout << city << " " << day << " " << dp[city][day] << endl; dp[city][day] = max((long long)attraction[city] + solveLeft(START-1, day - (city - START + 1) - 1, attraction), max((long long)attraction[city] + solveRight(city+1, day-2, attraction), max(solveRight(city+1, day-1, attraction), solveLeft(START-1, day - (city - START + 1), attraction)))); return dp[city][day]; } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { dp = vector<vector<long long int>>(n, vector<long long int>(d+1, -1)); N = n; D = d; START = start; /* for(int i = 0; i < n; ++i) values[i] = attraction[i]; */ return solveRight(start, d, attraction); } /* int main(){ int n, d, start; cin >> n >> start >> d; int cities[n]; for(int i = 0; i < n; ++i) cin >> cities[i]; cout<< findMaxAttraction(n, start, d, cities) << endl; 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...