oj.uz

Submission #685218

# Submission time Handle Problem Language Result Execution time Memory
685218 2023-01-23T17:13:30 Z Quan2003 Building Bridges (CEOI17_building) C++17
100 / 100
 86 ms 19184 KB 
#include <bits/stdc++.h>
#include <iostream> 
#include<vector>
using namespace std;
typedef long long ll;
const int sz = 4e5 + 1;
const int N = 4e5 + 5;
const int M = 4e5 + 5;
const int mod = 1e9 + 7; 
long long n,m,k,q,cnt;
long long w[N + 1];
long long h[N + 1];
long long dp[N + 1];
vector<int>adj[N + 1]; 
bool _Line_Comp_State; 
struct Line {
	// k is slope, m is intercept, p is intersection point
	mutable long long k, m, p;
	bool operator<(const Line& o) const {
		return _Line_Comp_State ? p < o.p : k < o.k;
	}
};
struct LineContainer : multiset<Line> {
	long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }

	bool isect(iterator x, iterator y) {
		if (y == end()) { 
			x->p = LLONG_MAX; 
			return false; 
		}
		if (x->k == y->k) {
			x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
		} else {
			x->p = div(y->m - x->m, x->k - y->k);
		}
		return x->p >= y->p;
	}
	void add(long long k, long long m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) {
			z = erase(z);
		}
		if (x != begin() && isect(--x, y)) {
			isect(x, y = erase(y));
		}
		while ((y = x) != begin() && (--x)->p >= y->p) {
			isect(x, erase(y));
		}
	}

	long long query(long long x) {
		assert(!empty());
		_Line_Comp_State = 1; 
		auto l = *lower_bound({0, 0, x}); 
		_Line_Comp_State = 0;
		return l.k * x + l.m;
	}
};
int main(){
     scanf("%d",&n);
     long long to = 0;
     for(int i = 1; i <= n; i++) cin>>h[i];
     for(int i = 1; i <= n; i++){
          cin>>w[i];
          to += w[i];
     }
     LineContainer lc;
     dp[1] = -w[1];
     lc.add(2 * h[1], -(long long) h[1] * h[1] - dp[1]); 
     for(int i = 2; i <= n; i++){
          dp[i] =  - lc.query(h[i]) - w[i] + (long long) h[i] * h[i];
          lc.add(2 * h[i],  -(long long) h[i] * h[i] - dp[i]);
     }
     cout<<dp[n] + to<<endl; 
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:60:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   60 |      scanf("%d",&n);
      |             ~^  ~~
      |              |  |
      |              |  long long int*
      |              int*
      |             %lld
building.cpp:60:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |      scanf("%d",&n);
      |      ~~~~~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9724 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9712 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 13148 KB Output is correct
2 Correct 76 ms 13132 KB Output is correct
3 Correct 71 ms 13240 KB Output is correct
4 Correct 66 ms 12952 KB Output is correct
5 Correct 68 ms 14076 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9724 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9712 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 73 ms 13148 KB Output is correct
7 Correct 76 ms 13132 KB Output is correct
8 Correct 71 ms 13240 KB Output is correct
9 Correct 66 ms 12952 KB Output is correct
10 Correct 68 ms 14076 KB Output is correct
11 Correct 82 ms 13176 KB Output is correct
12 Correct 86 ms 13088 KB Output is correct
13 Correct 69 ms 13088 KB Output is correct
14 Correct 75 ms 13240 KB Output is correct
15 Correct 86 ms 19184 KB Output is correct
16 Correct 67 ms 14164 KB Output is correct
17 Correct 57 ms 13048 KB Output is correct
18 Correct 58 ms 13064 KB Output is correct