Submission #708695

#TimeUsernameProblemLanguageResultExecution timeMemory
708695Green55Mountains (IOI17_mountains)C++17
100 / 100
59 ms32076 KiB
#include "mountains.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define xx first #define yy second #define all(v) (v).begin(), (v).end() // * dp[l][r] : r을 반드시 포함하여 l~r에서 지을 수 있는 최대 개수 // k[] = r에서 보이는 점들의 인덱스들을 순서대로 쓴 배열. // -> dp[l][r]은 k를 기준으로 partition을 나눠서, 각 최적을 합한 것과 같다. // k[i] = k[]에서 l의 lower bound. // opt(l ~ r) = 구간 [l~r]에서 최적 = max{l <= i <= r}(dp[l][i]) // dp[l][r] = opt(l ~ k[i]-1) + opt(k[i]+1, k[i+1]-1) + ...+ opt(k[-2]+1, k[-1]-1) + 1 int n, dp[2020][2020], opt[2020][2020]; ll h[2020]; int get_opt(int l, int r) { auto &ret = opt[l][r]; if(ret != -1) return ret; assert(dp[l][r] != -1); assert(dp[l][r] <= r-l+1); ret = dp[l][r]; if(l <= r-1) ret = max(ret, get_opt(l, r-1)); return ret; } bool canSee(int l, int mid, int r) { return (mid - l)*(h[r] - h[l]) - (r - l)*(h[mid] - h[l]) >= 0; } int maximum_deevs(vector<int> _y){ n = _y.size(); for(int i=1; i<=n; ++i) h[i] = _y[i-1]; for(int i=0; i<=n+1; ++i) for(int j=0; j<=n+1; ++j) dp[i][j] = opt[i][j] = -1; dp[1][1] = 1; for(int r=2; r<=n; ++r) { vector<int> ks = {r-1}; for(int l=r-2; l>=1; --l) if(canSee(l, ks.back(), r)) ks.push_back(l); ks.push_back(0); dp[r][r] = dp[r-1][r] = 1; int opt_sum = 1; // cout << "*** " << r << " : "; cout << endl; for(int ki=1; ki<ks.size(); ++ki) { int k2 = ks[ki-1], k1 = ks[ki]; for(int l=k1+1; l<k2; ++l) dp[l][r] = opt_sum + get_opt(l, k2-1); if(k1+1 <= k2-1) opt_sum += get_opt(k1+1, k2-1); dp[k1][r] = opt_sum; // cout << k1 << '~' << k2 << " : "; // for(int i=k1; i<k2; ++i) cout << dp[i][r] << ' '; cout << endl; } } return get_opt(1, n); }

Compilation message (stderr)

mountains.cpp: In function 'int maximum_deevs(std::vector<int>)':
mountains.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int ki=1; ki<ks.size(); ++ki) {
      |                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...