Submission #650267

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
650267	2022-10-13 09:35:45	alvinpiter	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	102 ms	3296 KiB

fancyfence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
Assume we already know the number of rectangles on the first (i - 1) fence.
Define f(i) as (i * i + i)/2;
If we are to add the i-th fence, then the new rectangles can be categorized into 3:
* It lies completely on the i-th fence. There are f(h[i]) * f(w[i]) such rectangles.
* The right end ends on the i-th fence while the left end lies on taller fence to the left of it.
  We don't want to consider the taller fence that comes before a fence lower than the i-th fence.
  Let's say the first lower fence to the left of the i-th fence is the j-th fence.
  There are (sumWidth(j + 1, i) * w[i]) * f(h[i]) such rectangles.
* The right end ends on the i-th fence while the left end lies on lower fences.
  Assume we keep the lower fences on a stack:
  h_i1 < h_i2 < h_i3 ...
  We can create rectangles whose height is at most h_i3 using the (i2 + 1)-th fence upto the i3-th fence.
  There are (sumWidth(i2 + 1, i3) * w[i]) * f(h_i3) such rectangles.
  We can do the same calculation for the (i1 + 1)-th fence upto the i2-th fence, and so on.
*/
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define MOD 1000000007
#define MAXN 100000
int n;
LL h[MAXN + 3], w[MAXN + 3], sumWidth[MAXN + 3], sumFhw = 0, ans = 0;
stack<int> st;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27