This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll itn;
#define ff first
#define ss second
string findSum(string str1, string str2)
{
if (str1.length() > str2.length())
swap(str1, str2);
string str = "";
ll n1 = str1.length(), n2 = str2.length();
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
ll carry = 0;
for (ll i = 0; i < n1; i++)
{
ll sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
str.push_back(sum % 10 + '0');
carry = sum / 10;
}
for (ll i = n1; i < n2; i++)
{
ll sum = ((str2[i] - '0') + carry);
str.push_back(sum % 10 + '0');
carry = sum / 10;
}
if (carry)
str.push_back(carry + '0');
reverse(str.begin(), str.end());
return str;
}
bool isSmaller(string str1, string str2)
{
ll n1 = str1.length(), n2 = str2.length();
if (n1 < n2)
return true;
if (n2 < n1)
return false;
for (ll i = 0; i < n1; i++)
if (str1[i] < str2[i])
return true;
else if (str1[i] > str2[i])
return false;
return false;
}
string findDiff(string str1, string str2)
{
if (isSmaller(str1, str2))
swap(str1, str2);
string str = "";
ll n1 = str1.length(), n2 = str2.length();
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
ll carry = 0;
for (ll i = 0; i < n2; i++) {
ll sub
= ((str1[i] - '0') - (str2[i] - '0') - carry);
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
for (ll i = n2; i < n1; i++) {
ll sub = ((str1[i] - '0') - carry);
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
reverse(str.begin(), str.end());
return str;
}
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 100007;
ll n, m, k;
ll a[1000007];
ll p[1000007];
ll s[1000007];
int main() {
cin >> n;
ll sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i != 0) {
p[i] = max(a[i - 1] - a[i] + 1, 0ll);
s[i] = max(a[i] - a[i - 1] + 1, 0ll);
sum2 += s[i];
}
}
ll ans = sum2;
for (int i = 0; i < n; i++) {
sum1 += p[i];
sum2 -= s[i];
ans = min(ans, max(sum1, sum2));
}
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |