oj.uz

Submission #284236

# Submission time Handle Problem Language Result Execution time Memory
284236 2020-08-27T04:45:02 Z 임성재(#5754) Discharging (NOI20_discharging) C++17
11 / 100
 886 ms 16504 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];

	return (x.se - s.se) * (f.fi - x.fi) >= (x.se - f.se) * (s.fi - f.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[n];
}

Compilation message

Discharging.cpp: In function 'int main()':
Discharging.cpp:50: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]
   50 |   while(idx+1 < v.size()) {
      |         ~~~~~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 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 886 ms 16464 KB Output is correct
2 Correct 840 ms 16308 KB Output is correct
3 Correct 833 ms 16360 KB Output is correct
4 Correct 840 ms 16432 KB Output is correct
5 Correct 846 ms 16504 KB Output is correct
6 Correct 831 ms 16376 KB Output is correct
7 Correct 842 ms 16332 KB Output is correct
8 Correct 850 ms 16400 KB Output is correct
9 Correct 873 ms 16348 KB Output is correct
10 Correct 855 ms 16472 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 Incorrect 1 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 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -