제출 #299861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299861		mohamedsobhi777	스카이라인 (IZhO11_skyline)	C++14	0 / 100	2079 ms	50684 KiB

skyline

#include<bits/stdc++.h>


#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 5e5 + 7 , mod = 1e9 + 7 ; 
const ll inf = 1e8 ; 
// How interesting!

int n; 
int a[N]; 
int dp[305][205][205] ; 

int solve(int i , int x , int y){
        if(~dp[i][x][y])
                return dp[i][x][y] ;
        if( i == n  + 2 )
                return 0 ; 
        int ret = 0 ; 
        int A = a[i-2] - x ; 
        int B = a[i-1] - y ; 
        int C = a[i] ;      

        for(int j = min({A , B , C}) ;j <= a[i] ;j ++){
                int mn = min(j , min({A , B , C}) ) ; 
                int mn2 = min(B - mn , C - mn) ;
                if(mn + mn2 < j)
                        break ; 
                mn2 = min(mn2 , j - mn) ;
                ret = max(ret ,2 * mn + mn2 + solve(i+1 , y + j , j ) ) ; 
        }

        return dp[i][x][y] = ret; 
}

int main(){
        ios_base::sync_with_stdio(0) ; 
        cin.tie(0) ;
        memset(dp , -1 , sizeof dp) ;
        cin >> n; 
        int ans = 0 ; 
        for(int i = 0 ;i < n;i++){
                cin >> a[i + 2] ; 
                ans += a[i + 2] * 3; 
        }
        cout<< ans - solve(2 , 0 , 0);
        return 0 ; 
}

• Subtask 1: 0 / 100