oj.uz

Submission #1019599

# Submission time Handle Problem Language Result Execution time Memory
1019599 2024-07-11T04:47:00 Z Minbaev Skyline (IZhO11_skyline) C++17
0 / 100
 65 ms 98396 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
 
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
 
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define int long long
#define pii pair<int,int>
 
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
 
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
 
const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;

int binpow(int a, int b){
	if(b == 0)return 1;
	if(b % 2 == 0){
		int c = binpow(a,b/2);
		return (c*c)%mod;
	}
	return (binpow(a,b-1)*a)%mod;
}

int divi(int a, int b){
	return (a*(binpow(b,mod-2)))%mod;
}

int n,m,k;
int dp[305][205][205];

void solve(){
	
	cin >> n;
	vector<int>v(n+1);
	for(int i = 1;i<=n;i++)
		cin >> v[i];
	
	for(int i = 1;i<=300;i++)
		for(int j = 0;j<=200;j++)
			for(int k = 0;k<=200;k++)
				dp[i][j][k] = inf;
	
	for(int i = 0;i<=v[1];i++)
		dp[2][v[2]][v[1]-i] = dp[1][v[1]-i][0] = i*3;
	
	
	for(int i = 2;i<=n;i++){
		for(int j = v[i];j>=0;j--)
			for(int k = v[i-1];k>=0;k--)
				umin(dp[i][j][k], dp[i][j+1][k]+3);
		
		for(int j = v[i];j>=0;j--)
			for(int k = v[i-1];k>=0;k--)
				umin(dp[i][j][k], dp[i][j+1][k+1]+5);
		
		if(n == i)continue;
		
		for(int j = min({v[i],v[i+1],v[i-1]});j>=0;j--)
			for(int k = v[i];k>=j;k--)
				umin(dp[i+1][v[i+1]-j][k-j], dp[i][k][j] + j*7);
		
	}
	
	cout << dp[n][0][0] << "\n";
	
	
	
	
}
 
 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);

	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();
 
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98348 KB Output is correct
2 Correct 33 ms 98388 KB Output is correct
3 Correct 34 ms 98236 KB Output is correct
4 Correct 35 ms 98384 KB Output is correct
5 Correct 50 ms 98396 KB Output is correct
6 Correct 38 ms 98388 KB Output is correct
7 Correct 40 ms 98356 KB Output is correct
8 Correct 38 ms 98340 KB Output is correct
9 Correct 39 ms 98196 KB Output is correct
10 Correct 38 ms 98396 KB Output is correct
11 Correct 47 ms 98384 KB Output is correct
12 Correct 37 ms 98188 KB Output is correct
13 Correct 42 ms 98384 KB Output is correct
14 Correct 46 ms 98392 KB Output is correct
15 Incorrect 65 ms 98320 KB Output isn't correct
16 Halted 0 ms 0 KB -