oj.uz

Submission #684938

# Submission time Handle Problem Language Result Execution time Memory
684938 2023-01-22T21:37:03 Z Ahmed57 Mountains (IOI17_mountains) C++14
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
int x[2012],y[2012];
int 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
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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