oj.uz

Submission #498742

# Submission time Handle Problem Language Result Execution time Memory
498742 2021-12-26T09:29:39 Z jiahng Discharging (NOI20_discharging) C++14
47 / 100
 1000 ms 880984 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define MOD 1000000007
#define maxn 1000010
#define INF (ll)1e18

int N;
int dp[maxn], T[maxn];
int f(pi line, int x){
	if (line == pi(-1,-1)) return INF;
	return line.f * x + line.s;
}

ld intersect(pi line1, pi line2){
	return (line2.s - line1.s) / (line1.f - line2.f);
}

struct node{
	int s,e,m,ver;
	node *l,*r;
	pi val = pi(-1,-1);
	
	node (int ss,int ee, int _ver){
		s = ss; e = ee; m = (s + e) / 2; ver = _ver;
	}
	void create_all(){
		if (s != e){
			l = new node(s,m,ver); r = new node(m+1,e,ver);
			l->create_all(); r->create_all();
		}
	}
		
	void upd(pi line, node *prev){
		val = prev->val;
		
		if (s == e){
			if (f(line, s) < f(val, s)) val = line;
			return;
		}
		if (val == pi(-1,-1)){
			val = line; l = prev->l; r = prev->r;
		}else if (intersect(line, val) < m){
			if (f(line, m) < f(val, m)) swap(val, line);
			r = prev->r;
			l = new node(s,m,ver);
			l->upd(line, prev->l);
		}else{
			if (f(line, m) < f(val, m)) swap(val, line);
			l = prev->l;
			r = new node(m+1,e,ver);
			r->upd(line, prev->r);
		}
	}
	int qry(int x){
		if (s == e) return f(val, x);
		if (x > m) return min(f(val, x), r->qry(x));
		else return min(f(val, x), l->qry(x));
	}
	void del(){
		if (s != e){
			if (l->ver == ver){
				l->del(); delete l;
			}
			if (r->ver == ver){
				r->del(); delete r;
			}
		}
	}
};
vector <node*> roots;
int suffmax[maxn];

int32_t main(){
    fast;
    
	cin >> N;
	FOR(i,1,N) cin >> T[i];
	DEC(i,N,1) suffmax[i] = max(suffmax[i+1], T[i]);
	stack <pi> st;
	int vercount = 1;
	node *root = new node(1,N,0);
	root->create_all();
	roots.pb(root);
	
	dp[N+1] = 0;
	DEC(i,N,1){
		//~ int mx = -1;
		//~ dp[i] = INF;
		//~ FOR(k,i,N) {
			//~ mx = max(mx, T[k]);
			//~ if (k == N || T[k+1] > mx) dp[i] = min(dp[i], dp[k+1] + mx * (N - i + 1));
		//~ }
		while (!st.empty() && st.top().f <= T[i]){
			st.pop();
			if (!st.empty()){
				roots.back()->del();
				roots.pop_back();
			}
		}
		
		if (!st.empty()){
			node *newroot = new node(1,N,vercount+1);
			vercount++;
			newroot->upd(pi(T[i],dp[st.top().s]), roots.back());
			roots.pb(newroot);
		}
		st.push(pi(T[i], i));
		
		dp[i] = suffmax[i] * (N - i + 1);
		if (!roots.empty()) dp[i] = min(dp[i], roots.back()->qry(N-i+1));
	}
	//~ FOR(i,1,N) cout << dp[i] << ' ';
	//~ cout << '\n';
	cout << dp[1];
	
	
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 3 ms 1612 KB Output is correct
4 Correct 3 ms 1484 KB Output is correct
5 Correct 2 ms 1740 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 2 ms 1740 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct
11 Correct 3 ms 1868 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 2 ms 1612 KB Output is correct
14 Correct 2 ms 1740 KB Output is correct
15 Correct 2 ms 1612 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 3 ms 1612 KB Output is correct
4 Correct 3 ms 1484 KB Output is correct
5 Correct 2 ms 1740 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 2 ms 1740 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct
11 Correct 3 ms 1868 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 2 ms 1612 KB Output is correct
14 Correct 2 ms 1740 KB Output is correct
15 Correct 2 ms 1612 KB Output is correct
16 Execution timed out 1121 ms 880984 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 180284 KB Output is correct
2 Correct 290 ms 180296 KB Output is correct
3 Correct 307 ms 180292 KB Output is correct
4 Correct 286 ms 180268 KB Output is correct
5 Correct 290 ms 180232 KB Output is correct
6 Correct 293 ms 180236 KB Output is correct
7 Correct 287 ms 180276 KB Output is correct
8 Correct 308 ms 180284 KB Output is correct
9 Correct 309 ms 180240 KB Output is correct
10 Correct 300 ms 180276 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Correct 2 ms 1612 KB Output is correct
17 Correct 3 ms 1612 KB Output is correct
18 Correct 3 ms 1484 KB Output is correct
19 Correct 2 ms 1740 KB Output is correct
20 Correct 2 ms 1484 KB Output is correct
21 Correct 3 ms 1612 KB Output is correct
22 Correct 2 ms 1740 KB Output is correct
23 Correct 2 ms 1868 KB Output is correct
24 Correct 2 ms 1740 KB Output is correct
25 Correct 3 ms 1868 KB Output is correct
26 Correct 2 ms 1612 KB Output is correct
27 Correct 2 ms 1612 KB Output is correct
28 Correct 2 ms 1740 KB Output is correct
29 Correct 2 ms 1612 KB Output is correct
30 Correct 1 ms 716 KB Output is correct
31 Correct 1 ms 716 KB Output is correct
32 Correct 1 ms 716 KB Output is correct
33 Correct 1 ms 716 KB Output is correct
34 Correct 1 ms 588 KB Output is correct
35 Correct 2 ms 716 KB Output is correct
36 Correct 1 ms 716 KB Output is correct
37 Correct 2 ms 716 KB Output is correct
38 Correct 1 ms 716 KB Output is correct
39 Correct 1 ms 716 KB Output is correct
40 Correct 2 ms 588 KB Output is correct
41 Correct 1 ms 716 KB Output is correct
42 Correct 1 ms 716 KB Output is correct
43 Correct 2 ms 1612 KB Output is correct
44 Correct 1 ms 716 KB Output is correct
45 Correct 1 ms 716 KB Output is correct
46 Correct 1 ms 716 KB Output is correct
47 Correct 1 ms 716 KB Output is correct
48 Correct 1 ms 716 KB Output is correct
49 Correct 1 ms 716 KB Output is correct
50 Correct 1 ms 588 KB Output is correct

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Correct 2 ms 1612 KB Output is correct
17 Correct 3 ms 1612 KB Output is correct
18 Correct 3 ms 1484 KB Output is correct
19 Correct 2 ms 1740 KB Output is correct
20 Correct 2 ms 1484 KB Output is correct
21 Correct 3 ms 1612 KB Output is correct
22 Correct 2 ms 1740 KB Output is correct
23 Correct 2 ms 1868 KB Output is correct
24 Correct 2 ms 1740 KB Output is correct
25 Correct 3 ms 1868 KB Output is correct
26 Correct 2 ms 1612 KB Output is correct
27 Correct 2 ms 1612 KB Output is correct
28 Correct 2 ms 1740 KB Output is correct
29 Correct 2 ms 1612 KB Output is correct
30 Execution timed out 1121 ms 880984 KB Time limit exceeded
31 Halted 0 ms 0 KB -