Submission #219762

#	Time	Username	Problem	Language	Result	Execution time	Memory
219762		Mercenary	Mountains (IOI17_mountains)	C++14	100 / 100	38 ms	8448 KiB

mountains

#include"mountains.h"

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e3 + 5;
const int mod = 1e9 + 7;

int n;
vector<int> a;
int f[maxn][maxn];
int solve(int l , int r){
    if(l == r)return 1;
    if(l > r)return 0;
    int & res = f[l][r];
    if(res > 0)return res;
    int mx = l;
    for(int i = l ; i <= r ; ++i)if(a[mx] < a[i])mx = i;
    int sum = 1;//choose mx
    auto See = [&](int i , int j , int k)->bool{
       return 1ll * (a[i] - a[j]) * (i - k) > 1ll * (a[i] - a[k]) * (i - j);
    };
    for(int i = mx + 1 ; i <= r ; ){
        int j = i + 1;
        for( ; j <= r ; ++j){
            if(See(mx,i,j)){
                if(j == r)sum += solve(i + 1,  r);
            }else{
                sum += solve(i + 1 , j - 1);
                break;
            }
        }
        i = j;
    }
    for(int i = mx - 1 ; i >= l ; ){
        int j = i - 1;
        for( ; j >= l ; --j){
            if(See(j,i,mx)){
                if(j == l)sum += solve(l ,  i - 1);
            }else{
                sum += solve(j + 1 , i - 1);
                break;
            }
        }
        i = j;
    }
    return res = max(sum , solve(l , mx - 1) + solve(mx + 1 , r));
}
int maximum_deevs(vector<int> A) {
    a = A;
    n = a.size();
    return solve(0 , n - 1);
}
//int main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    if(fopen(taskname".INP","r")){
//		freopen(taskname".INP", "r",stdin);
//		freopen(taskname".OUT", "w",stdout);
//    }
//
//}

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