oj.uz

Submission #284242

# Submission time Handle Problem Language Result Execution time Memory
284242 2020-08-27T04:49:37 Z 임성재(#5754) Discharging (NOI20_discharging) C++17
11 / 100
 874 ms 16156 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n;
ll t[1000010];
ll dp[1000010];
vector<pll> v;

bool cross(int i, int j, ll x) {
	return v[i].fi * x + v[i].se > v[j].fi * x + v[j].se;
}

bool chk(pll x) {
	pll f = v[v.size()-2];
	pll s = v[v.size()-1];

	//cout << (x.se - s.se) * (f.fi - x.fi) << " " << (x.se - f.se) * (s.fi - x.fi) << endl;

	return (x.se - s.se) * (f.fi - x.fi) >= (x.se - f.se) * (s.fi - x.fi) ;
}

int main() {
	cin >> n;

	for(int i=1; i<=n; i++) {
		cin >> t[i];
		t[i] = max(t[i], t[i-1]);
	}

	v.eb(n, 0);
	int idx = 0;

	for(int i=1; i<=n; i++) {
		dp[i] = INF;

		if(t[i] == t[i+1]) continue;

		while(idx+1 < v.size()) {
			if(cross(idx, idx+1, t[i])) idx++;
			else break;
		}

		dp[i] = v[idx].fi * t[i] + v[idx].se;

		while(v.size() > 1 && chk(mp(n-i, dp[i]))) v.pop_back();

		v.eb(n - i, dp[i]);

		//cout << dp[i] << " " << v.size() << endl;
	}

	cout << dp[n];
}

Compilation message

Discharging.cpp: In function 'int main()':
Discharging.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   while(idx+1 < v.size()) {
      |         ~~~~~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 16104 KB Output is correct
2 Correct 845 ms 15920 KB Output is correct
3 Correct 848 ms 15996 KB Output is correct
4 Correct 838 ms 16060 KB Output is correct
5 Correct 866 ms 16000 KB Output is correct
6 Correct 874 ms 16004 KB Output is correct
7 Correct 839 ms 16156 KB Output is correct
8 Correct 860 ms 16020 KB Output is correct
9 Correct 840 ms 16020 KB Output is correct
10 Correct 833 ms 15992 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -