#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define DISABLE_PRINTF
#ifdef DISABLE_PRINTF
#define printf(...)
#endif // DISABLE_PRINTF
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
for(int i = 1; i <= n; ++i)
{
cin >> a[i] >> b[i];
}
int A = 0;
int B = 0;
for(int i = 1; i <= n; ++i)
{
A += a[i], B += b[i];
}
if(A == B)
{
/// solve it
int ans = 0;
int aid = 1, bid = 1;
for(; bid <= n; ++bid)
{
for(; b[bid] > 0; ++aid)
{
int take = min(a[aid], b[bid]);
b[bid] -= take;
a[aid] -= take;
ans += take * abs(bid - aid);
if(b[bid] == 0)
{
break;
}
}
}
cout << ans;
}
else if(A == B + 1)
{
vector<int> pref(n + 1), suff(n + 2);
vector<int> prefLast(n + 1), suffLast(n + 2);
vector<int> bcopy = b;
vector<int> acopy = a;
/// calc the pref
int aid = 1;
for(int i = 1; i <= n; ++i)
{
pref[i] = pref[i - 1];
for(; b[i] > 0; aid += (a[aid] == 0))
{
int take = min(a[aid], b[i]);
b[i] -= take;
a[aid] -= take;
pref[i] += abs(i - aid) * take;
if(take == 0) continue;
prefLast[i] = aid;
}
}
a = acopy;
b = bcopy;
/// calc the suff
aid = n;
for(int i = n; i >= 1; --i)
{
suff[i] = suff[i + 1];
for(; b[i] > 0; aid -= (a[aid] == 0))
{
int take = min(a[aid], b[i]);
b[i] -= take;
a[aid] -= take;
suff[i] += abs(aid - i) * take;
if(take == 0) continue;
suffLast[i] = aid;
}
}
a = acopy;
b = bcopy;
/// calc ferPref and ferSuff
vector<int> ferPref(n + 1), ferSuff(n + 2);
vector<int> potPref(n + 1), potSuff(n + 2);
for(int i = 1; i <= n; ++i)
{
ferPref[i] = ferPref[i - 1] + a[i];
ferSuff[n + 1 - i] = ferSuff[n + 1 - i + 1] + a[n + 1 - i];
potPref[i] = potPref[i - 1] + b[i];
potSuff[n + 1 - i] = potSuff[n + 1 - i + 1] + b[n + 1 - i];
}
/// calc the answer
int ans = min(pref[n], suff[1]);
vector<int> potIds;
for(int i = 1; i <= n; ++i)
{
if(b[i] > 0)
{
potIds.push_back(i);
}
}
printf("|potIds| = %d\n", (int) potIds.size());
for(int j = 0; j < potIds.size() - 1; ++j)
{
int l = potIds[j];
int r = potIds[j + 1];
int initAns = pref[l] + suff[r];
int curAns = initAns;
/// find the location of fertilizer
int fl = prefLast[l];
int fr = suffLast[r];
int flSum = ferPref[fl];
int frSum = ferSuff[fr];
int blSum = potPref[l];
int brSum = potSuff[r];
printf("(l, r) = (%d, %d)\n(fl, fr) = (%d, %d)\n(flSum, frSum) = (%d, %d)\n(blSum, brSum) = (%d, %d)\n", l, r, fl, fr, flSum, frSum, blSum, brSum);
if(fl == fr) continue;
assert(blSum + brSum == potPref[n]);
assert(flSum + frSum == ferPref[n] - 1 || flSum + frSum == ferPref[n]);
if(flSum == blSum && frSum == brSum)
{
for(int q = fl + 1; q < fr; ++q)
{
if(a[q] > 0)
{
curAns = min({curAns,
initAns + abs(l - q) - abs(fl - q),
initAns + abs(r - q) - abs(fr - q)});
break;
}
assert(q != fr - 1);
}
}
else if(flSum < blSum )
{
curAns = min(curAns, initAns + abs(r - fl) - abs(r - fr));
}
else if(frSum < brSum)
{
curAns = min(curAns, initAns + abs(l - fr) - abs(l - fl));
}
else
{
assert(false);
}
ans = min(ans, curAns);
}
cout << ans << '\n';
}
}
signed main()
{
#ifdef EVAL
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
#endif // EVAL
solve();
}
Compilation message
bulves.cpp: In function 'void solve()':
bulves.cpp:106:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int j = 0; j < potIds.size() - 1; ++j)
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
13 ms |
2004 KB |
Output is correct |
| 6 |
Correct |
42 ms |
4228 KB |
Output is correct |
| 7 |
Correct |
85 ms |
8148 KB |
Output is correct |
| 8 |
Correct |
62 ms |
8148 KB |
Output is correct |
| 9 |
Correct |
62 ms |
8148 KB |
Output is correct |
| 10 |
Correct |
50 ms |
8148 KB |
Output is correct |
| 11 |
Correct |
48 ms |
8144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
368 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
13 ms |
2004 KB |
Output is correct |
| 6 |
Correct |
42 ms |
4228 KB |
Output is correct |
| 7 |
Correct |
85 ms |
8148 KB |
Output is correct |
| 8 |
Correct |
62 ms |
8148 KB |
Output is correct |
| 9 |
Correct |
62 ms |
8148 KB |
Output is correct |
| 10 |
Correct |
50 ms |
8148 KB |
Output is correct |
| 11 |
Correct |
48 ms |
8144 KB |
Output is correct |
| 12 |
Incorrect |
33 ms |
13164 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
368 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
368 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
