oj.uz

Submission #299861

# Submission time Handle Problem Language Result Execution time Memory
299861 2020-09-15T21:37:02 Z mohamedsobhi777 Skyline (IZhO11_skyline) C++14
0 / 100
 2000 ms 50684 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 50560 KB Output is correct
2 Correct 29 ms 50560 KB Output is correct
3 Correct 29 ms 50552 KB Output is correct
4 Correct 30 ms 50560 KB Output is correct
5 Correct 29 ms 50552 KB Output is correct
6 Correct 31 ms 50560 KB Output is correct
7 Correct 30 ms 50552 KB Output is correct
8 Correct 31 ms 50552 KB Output is correct
9 Correct 37 ms 50552 KB Output is correct
10 Correct 51 ms 50684 KB Output is correct
11 Correct 136 ms 50576 KB Output is correct
12 Correct 91 ms 50552 KB Output is correct
13 Correct 186 ms 50576 KB Output is correct
14 Correct 469 ms 50584 KB Output is correct
15 Execution timed out 2079 ms 50560 KB Time limit exceeded
16 Halted 0 ms 0 KB -