oj.uz

Submission #169136

# Submission time Handle Problem Language Result Execution time Memory
169136 2019-12-18T14:55:05 Z CaroLinda Building Bridges (CEOI17_building) C++14
100 / 100
 121 ms 66552 KB 
#include <bits/stdc++.h>

#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()

const int MAXN = 1e5+10 ;
const int MAX = 1e6+10, pat = 1e3+10 ;
const ll inf = 1e18+5 ;

using namespace std ;

struct Line
{

	ll a , b ;

	Line(ll a = 1 , ll b = 0) : a(a) , b(b) {}

	ll get(ll x ) 
	{
		if( a > 0 ) return inf ;
		return a*x + b ;
	}

	void print() { printf("%lld %lld\n" ,a , b ) ; }

} tree[MAX*4] ;

int n ;
ll sw[MAXN] , dp[MAXN] , h[MAXN]  ;
bool vis[MAX*4] ;

ll q(ll x) { return x*x ; }

int m(int l, int r) { return (l+r)>>1 ; }

void upd(int pos, int l, int r, Line v)
{

	if( !vis[pos] ) 
	{
		vis[pos] = true ;
		tree[pos] = v ;
		return ;
	}

	if( tree[pos].get(l) <= v.get(l) && tree[pos].get(r) <= v.get(r) ) return ;
	else if( tree[pos].get(l) > v.get(l) && tree[pos].get(r) > v.get(r) )
		return (void)(tree[pos] = v ) ;

	if( tree[pos].get(l) > v.get(l) ) swap( tree[pos] , v ) ;
	if( tree[pos].get( m(l,r) ) < v.get( m(l,r) ) ) upd( 2*pos+1, m(l,r)+1, r, v ) ;
	else
	{
		swap( tree[pos] , v ) ;
		upd( 2*pos , l , m(l,r) , v ) ;
	}

}

ll getAns(int pos, int l, int r, ll x)
{

	ll ans = tree[pos].get(x) ;
	if(l==r) return ans ;
	if( x <= m(l,r) ) return min(ans, getAns(pos*2,l,m(l,r) , x) ) ;
	return min( ans , getAns(pos*2+1,m(l,r)+1,r, x) ) ;
}

void print(int pos, int l, int r)
{
	if( l == r ) 
	{
		printf("%d %d -> " , l, r) ;
		tree[pos].print() ;
		return ;
	}
	print(pos*2,l,m(l,r)) ;
	printf("%d %d -> " , l, r) ;
		tree[pos].print() ;
	print(pos*2+1,m(l,r)+1, r) ;
}

int main()
{

	scanf("%d", &n ) ;
	lp(i,1,n+1) scanf("%lld",&h[i]) ;
	lp(i,1,n+1)
	{
		scanf("%lld", &sw[i]) ;
		sw[i] += sw[i-1] ;
	}

	upd( 1 , 0 , MAX-5 , Line(h[n]*(-2) , q(h[n]) + sw[n-1]  )  ) ;
	
	for(int i = n-1 ; i > 0 ; i-- )
	{
		
		dp[i] = getAns( 1 , 0 , MAX-5 , h[i] )  - sw[i] + q(h[i]) ;
		upd(1,0,MAX-5 , Line( h[i] * (-2) , q( h[i] ) + sw[i-1] + dp[i] )  ) ;

	}

	printf("%lld\n" , dp[1] ) ;
 
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n ) ;
  ~~~~~^~~~~~~~~~~
building.cpp:96:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  lp(i,1,n+1) scanf("%lld",&h[i]) ;
              ~~~~~^~~~~~~~~~~~~~
building.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &sw[i]) ;
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 53 ms 62968 KB Output is correct
3 Correct 53 ms 62968 KB Output is correct
4 Correct 52 ms 62968 KB Output is correct
5 Correct 53 ms 63044 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 66424 KB Output is correct
2 Correct 116 ms 66388 KB Output is correct
3 Correct 116 ms 66448 KB Output is correct
4 Correct 114 ms 66296 KB Output is correct
5 Correct 109 ms 66524 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 53 ms 62968 KB Output is correct
3 Correct 53 ms 62968 KB Output is correct
4 Correct 52 ms 62968 KB Output is correct
5 Correct 53 ms 63044 KB Output is correct
6 Correct 116 ms 66424 KB Output is correct
7 Correct 116 ms 66388 KB Output is correct
8 Correct 116 ms 66448 KB Output is correct
9 Correct 114 ms 66296 KB Output is correct
10 Correct 109 ms 66524 KB Output is correct
11 Correct 121 ms 66552 KB Output is correct
12 Correct 120 ms 66436 KB Output is correct
13 Correct 107 ms 66424 KB Output is correct
14 Correct 121 ms 66544 KB Output is correct
15 Correct 110 ms 66424 KB Output is correct
16 Correct 109 ms 66552 KB Output is correct
17 Correct 84 ms 66424 KB Output is correct
18 Correct 84 ms 66424 KB Output is correct