제출 #247432

#제출 시각아이디문제언어결과실행 시간메모리
247432ritikpatel05Sličice (COCI19_slicice)C++17
90 / 90
250 ms2552 KiB
/* Author: Ritik Patel */ //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& STL DEBUGGER &&&&&&&&&&&&&&&&&&&&&&&&&&& // #define _GLIBCXX_DEBUG // Iterator safety; out-of-bounds access for Containers, etc. // #pragma GCC optimize "trapv" // abort() on (signed) integer overflow. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& LIBRARIES &&&&&&&&&&&&&&&&&&&&&&&&&&& #include <bits/stdc++.h> using namespace std; /*#include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update template<typename T, typename V = __gnu_pbds::null_type> using ordered_set = __gnu_pbds::tree<T, V, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; */ //find_by_order()->returns an iterator to the k-th largest element(0-based indexing) //order_of_key()->Number of items that are strictly smaller than our item //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEFINES &&&&&&&&&&&&&&&&&&&&&&&&&&& #define int long long int // #define ll long long int #define all(i) i.begin(), i.end() #define sz(a) (int)a.size() // #define ld long double // const ld PI = 3.141592; const int dx4[4] = {0, 1, 0, -1}; const int dy4[4] = {-1, 0, 1, 0}; const int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0}; const int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEBUG &&&&&&&&&&&&&&&&&&&&&&&&&&& #define XOX vector<string> vec_splitter(string s) { for(char& c: s) c = c == ','? ' ': c; stringstream ss; ss << s; vector<string> res; for(string z; ss >> z; res.push_back(z)); return res; } void debug_out(vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx) { cerr << endl; } template <typename Head, typename... Tail> void debug_out(vector<string> args, int idx, Head H, Tail... T) { if(idx > 0) cerr << ", "; stringstream ss; ss << H; cerr << args[idx] << " = " << ss.str(); debug_out(args, idx + 1, T...); } #ifdef XOX #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__) #else #define debug(...) 42 #endif //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& CODE &&&&&&&&&&&&&&&&&&&&&&&&&&& int N, M, K; const int MAXN = 505; int score[MAXN]; int curr[MAXN]; int memo[MAXN][MAXN]; const int MX = 1e10; int dp(int id, int left){ if(left < 0){ return -MX; } if(id == N){ if(left == 0){ return 0; } else { return -MX; } } auto &res = memo[id][left]; if(res != -1){ return res; } res = 0; int togive = M - curr[id]; for(int i = 0; i <= togive; ++i){ res = max(res, dp(id + 1, left - i) + score[curr[id] + i]); } return res; } void solve(){ memset(memo, -1, sizeof(memo)); cin >> N >> M >> K; for(int i = 0; i < N; ++i){ cin >> curr[i]; } for(int i = 0; i <= M; ++i){ cin >> score[i]; } cout << dp(0, K) << '\n'; } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int T = 1; // cin >> T; for(int i = 1; i <= T; ++i){ // brute(); solve(); } return 0; } /* Sample inp */
#Verdict Execution timeMemoryGrader output
Fetching results...