oj.uz

Submission #652427

# Submission time Handle Problem Language Result Execution time Memory
652427 2022-10-22T14:59:45 Z JooDdae Mountains (IOI17_mountains) C++17
0 / 100
 1 ms 340 KB 
#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] += s;
        }
    }
    
    return dp[n][1];
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -