oj.uz

Submission #922678

# Submission time Handle Problem Language Result Execution time Memory
922678 2024-02-06T00:42:57 Z thunopro Skyline (IZhO11_skyline) C++14
100 / 100
 113 ms 58684 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 200009 
#define ll long long 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 

const int mod = 1e9+7; 
const int INF = 1e9; 

typedef vector<int> vi; 
typedef pair<int,int> pii;
typedef vector<pii> vii;  
typedef vector<ll> vl;

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a > mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

template <typename T> void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template <typename T> void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ;
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ;
}

int n ; 
int a [maxn] ; 

int dp [309][209][209] ; 

int calc ( int pos , int h1 , int h2 ) 
{
	if ( pos == n+1 ) return 0 ; 
	int &res = dp [pos][h1][h2] ; 
	if ( res+1 ) return res ; 
	res = INF ; 
	if ( h1 ) 
	{
		res = min (res,calc(pos,h1-1,h2)+3) ; 
		if ( h2 ) 
		{
			res = min (res,calc(pos,h1-1,h2-1)+5) ; 
			if ( h1 <= min (h2,a[pos+2])) res = min (res,calc(pos+1,h2-h1,a[pos+2]-h1)+7*h1) ; 
		}
	}
	else res = min (res,calc(pos+1,h2,a[pos+2])) ; 
	return res ; 
}

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

Compilation message

skyline.cpp: In function 'void rf()':
skyline.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 53848 KB Output is correct
2 Correct 7 ms 53852 KB Output is correct
3 Correct 8 ms 53852 KB Output is correct
4 Correct 7 ms 53852 KB Output is correct
5 Correct 7 ms 53852 KB Output is correct
6 Correct 8 ms 53852 KB Output is correct
7 Correct 8 ms 53852 KB Output is correct
8 Correct 7 ms 53852 KB Output is correct
9 Correct 9 ms 53852 KB Output is correct
10 Correct 9 ms 54108 KB Output is correct
11 Correct 17 ms 55064 KB Output is correct
12 Correct 10 ms 54108 KB Output is correct
13 Correct 19 ms 55132 KB Output is correct
14 Correct 25 ms 55644 KB Output is correct
15 Correct 76 ms 57688 KB Output is correct
16 Correct 75 ms 57176 KB Output is correct
17 Correct 110 ms 58684 KB Output is correct
18 Correct 106 ms 58460 KB Output is correct
19 Correct 98 ms 58288 KB Output is correct
20 Correct 113 ms 58460 KB Output is correct