제출 #624354

#제출 시각아이디문제언어결과실행 시간메모리
624354yuto1115휴가 (IOI14_holiday)C++17
0 / 100
366 ms65536 KiB
#include"holiday.h" #include <bits/stdc++.h> #define rep(i, n) for(ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i) #define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i) #define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i) #define pb push_back #define eb emplace_back #define SZ(a) int(a.size()) #define all(a) a.begin(), a.end() using namespace std; using ll = long long; using P = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vp = vector<P>; using vvp = vector<vp>; using vb = vector<bool>; using vvb = vector<vb>; using vs = vector<string>; const int inf = 1001001001; const ll linf = 1001001001001001001; template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } vl get_max(const vi &v, int d, int s) { int n = SZ(v); vl res(d + 1); if (!n) return res; vvi ls(n, vi(n + 1)); multiset<int> st; rep(i, n) { st.insert(v[i]); auto it = st.end(); rep(j, i + 1) { --it; ls[i][j + 1] = ls[i][j] + *it; } } auto f = [&](int i, int num) -> ll { assert(0 <= i and i < n); assert(0 <= num); return ls[i][min(num, i + 1)]; }; // int now = 0; rep2(i, s, d + 1) { rep(j, n) { if (s * (j + 1) > i) break; chmax(res[i], f(j, i - s * (j + 1))); } // res[i] = f(now, i - s * (now + 1)); // while (now + 1 < n and s * (now + 2) <= i) { // ll l = f(now + 1, i - s * (now + 2)); // if (chmax(res[i], l)) ++now; // else break; // } } return res; } ll findMaxAttraction(int n, int start, int d, int attraction[]) { vi l, r; rrep(i, start) l.pb(attraction[i]); rep2(i, start + 1, n) r.pb(attraction[i]); ll ans = 0; rep(_, 2) { vl x = get_max(l, d, 1); vl y = get_max(r, d, 2); rep(i, d + 1) chmax(ans, x[i] + y[d - i]); rep(i, d) chmax(ans, x[i] + y[d - 1 - i] + attraction[start]); swap(l, r); } 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...