Submission #652428

#	Time	Username	Problem	Language	Result	Execution time	Memory
652428		JooDdae	Mountains (IOI17_mountains)	C++17	100 / 100	29 ms	14216 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct point{
   ll x, y;
   bool operator < (const point &a)const{
       return tie(x, y) < tie(a.x, a.y);
   }
   bool operator <= (const point &a)const{
       return tie(x, y) <= tie(a.x, a.y);
   }
   point operator - (const point &a)const{
       return {x-a.x, y-a.y};
   }
   bool operator == (const point &a)const{
       return tie(x, y) == tie(a.x, a.y);
   }
};

ll cross(point a, point b){
   return a.x * b.y - a.y * b.x;
}
int ccw(point a, point b, point c){
   ll re = cross(b-a, c-a);
   return re > 0 ? 1 : re < 0 ? -1 : 0;
}

int dp[2020][2020];

int maximum_deevs(vector<int> y) {
    int n = y.size();

    for(int i=1;i<=n;i++) {
        dp[i][i] = dp[i][i-1] = 1;
        for(int j=i-2, k=i-1, s=1;j>=1;j--) {
            if(ccw({j, y[j-1]}, {k, y[k-1]}, {i, y[i-1]}) >= 0) {
                s += dp[k-1][j+1], k = j;
            } else {
                dp[i][j] += dp[k-1][j];
            }
            dp[i][j] = max(dp[i-1][j], dp[i][j]+s);
        }
    }
    
    return dp[n][1];
}

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