제출 #684940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684940		Ahmed57	Mountains (IOI17_mountains)	C++14	100 / 100	38 ms	16020 KiB

mountains

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
long long x[2012],y[2012];
long long ccw(int a,int b,int c){
    return (x[b]-x[a])*(y[c]-y[a])-(y[b]-y[a])*(x[c]-x[a]);
}
int maximum_deevs(vector<int>a ){
    int n = a.size();
    for(int i = 0;i<n;i++){
        x[i] = i;
        y[i] = a[i];
    }
    int dp[n][n];
    memset(dp,0,sizeof dp);
    for(int r = 0;r<n;r++){
        dp[r][r] = 1;
        int last = r;
        int sum = 1;
        for(int l = r-1;l>=0;l--){
            dp[l][r] = dp[l][r-1];
            if(ccw(l,last,r)>=0){
                sum+=dp[l+1][last-1];
                last = l;
                dp[l][r] = max(dp[l][r],sum);
            }else{
                dp[l][r] = max(dp[l][r],sum+dp[l][last-1]);
            }
        }
    }
    return dp[0][n-1];
}
//signed main() {
  //  cout<<maximum_deevs({0,1,2});
//}

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