제출 #319999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319999		LifeHappen__	Mountains (IOI17_mountains)	C++14	100 / 100	54 ms	16364 KiB

mountains

#ifndef LOCAL
#include "mountains.h"
#endif // LOCAL

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define forinc(a,b,c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a,b,c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a,b) for(auto &a:b)
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ii pair<int,int>
#define fi first
#define se second
#define ar array
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

const int N=2005;
int n;
int dp[N][N];

int maximum_deevs(vector<int> y){
   auto ccw=[&](int i,int j,int k){
      return (long long)(y[i]-y[j])*(i-k)>(long long)(y[i]-y[k])*(i-j);
   };
   function<int(int,int)> solve=[&](int l,int r){
      if(l>r) return 0;
      if(l==r) return 1;
      if(dp[l][r]!=-1) return dp[l][r];
      int maxi=l;
      forinc(i,l,r) if(y[maxi]<y[i]) maxi=i;
      int tot=1;
      for(int i=maxi+1; i<=r; ){
         int j=i+1;
         for(; j<=r; ++j){
            if(ccw(maxi,i,j)) {if(j==r) tot+=solve(i+1,r);}
            else{
               tot+=solve(i+1,j-1);
               break;
            }
         }
         i=j;
      }
      for(int i=maxi-1; i>=l; ){
         int j=i-1;
         for(; j>=l; --j){
            if(ccw(j,i,maxi)){
               if(j==l) tot+=solve(l,i-1);
            } else{
               tot+=solve(j+1,i-1);
               break;
            }
         }
         i=j;
      }
      return dp[l][r]=max(tot, solve(l,maxi-1)+solve(maxi+1,r));
   };
   reset(dp,-1);
   return solve(0,y.size()-1);
}

#ifdef LOCAL
int32_t main(){
   fasty;

   cin>>n;
   vector<int> y(n);
   forv(v,y) cin>>v;
   cout<<maximum_deevs(y)<<'\n';
}
#endif //LOCAL

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30