oj.uz

Submission #262474

# Submission time Handle Problem Language Result Execution time Memory
262474 2020-08-13T01:12:03 Z Cantfindme Discharging (NOI20_discharging) C++17
11 / 100
 911 ms 18168 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 1000010;

#define ld long double
deque <pi> dq;
int n;
int T[maxn];
int jump[maxn];

int f(pi line, int x) {
	return line.f * x + line.s;
}

int query(int x) {
	while (dq.size() > 1) {
		if (f(dq[0],x) > f(dq[1],x)) dq.pop_front();
		else break;
	}
	return f(dq[0],x);
}

ld intersect(pi p1, pi p2) {
	return (ld) (p2.s - p1.s) / (p1.f - p2.f);
}

void insert(int m, int c) {
	pi line = pi(m,c);
	int s = dq.size();
	while (s > 1) {
		s = dq.size();
		if (intersect(dq.back(),line) <= intersect(dq[s-2],line)) dq.pop_back();
		else break;
	}
	dq.push_back(line);
}

int32_t main() {
	//FAST
	cin >> n;
	for (int i =1;i<=n;i++) cin >> T[i];
	
	pi curmax = pi(0,0);
	for (int i =1;i<=n;i++) {
		if (T[i] > curmax.f) {
			jump[i] = curmax.s;
			curmax = pi(T[i],i);
		}
	}
	
	int curx = curmax.s;
	insert(T[curx], 0);
	
	int bestprev = query(n - curx + 1);
	curx = jump[curx];
	
	while (curx != 0) {
		cout << curx << " " << T[curx] << " " << bestprev << "\n";
		insert(T[curx], bestprev);
		bestprev = query((n - curx + 1));
		curx = jump[curx];
	}
	cout << bestprev;
	
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 17968 KB Output is correct
2 Correct 833 ms 18060 KB Output is correct
3 Correct 840 ms 18168 KB Output is correct
4 Correct 834 ms 17916 KB Output is correct
5 Correct 911 ms 18040 KB Output is correct
6 Correct 829 ms 18168 KB Output is correct
7 Correct 831 ms 18040 KB Output is correct
8 Correct 835 ms 18168 KB Output is correct
9 Correct 831 ms 18040 KB Output is correct
10 Correct 834 ms 18040 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -