oj.uz

Submission #912367

# Submission time Handle Problem Language Result Execution time Memory
912367 2024-01-19T10:24:21 Z vjudge1 Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 70 ms 7372 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define ent "\n"

const int inf = (int)1e9 + 100;
const int maxn = 5e5 + 100;
const ll INF = (ll)1e18;
const int MOD = 1e9 + 7;
const int maxl = 62500;
const ll P = 31, T = 0;

int n;
int a[maxn];
int b[maxn];
int mx[maxn];

void test(){
	cin >> n;
	vector<int> v;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		if(a[i] > b[i]){
			v.push_back(i);
		}
	}
	ll ans = 0;
	for(int i = n; i > 0; i--){
		if(a[i] > b[i]) continue;
		while(a[i] < b[i]){
			int cnt = min(b[i] - a[i], a[v.back()] - b[v.back()]);
			a[i] += cnt; a[v.back()] -= cnt;
			mx[i] = max(mx[i], abs(v.back() - i));
			ans += 1ll * cnt * abs(v.back() - i);
			if(a[v.back()] == b[v.back()]) v.pop_back();
		}
	}
	int add = 0;
	if(v.size()){
		for(int i = 1; i <= n; i++){
			add = min(add, abs(i - v.back()) - mx[i]);
		}
	}
	cout << ans + add;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // #ifndef ONLINE_JUDGE
	//     freopen("input.txt", "r", stdin);
	//     freopen("output.txt", "w", stdout);
    // #endif
    int t = 1;
    if(T) cin >> t;
    while(t--) test();
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 7 ms 4836 KB Output is correct
5 Correct 15 ms 5116 KB Output is correct
6 Correct 33 ms 5592 KB Output is correct
7 Correct 70 ms 7372 KB Output is correct
8 Correct 54 ms 7036 KB Output is correct
9 Correct 54 ms 7372 KB Output is correct
10 Correct 52 ms 7368 KB Output is correct
11 Correct 47 ms 7284 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 7 ms 4836 KB Output is correct
5 Correct 15 ms 5116 KB Output is correct
6 Correct 33 ms 5592 KB Output is correct
7 Correct 70 ms 7372 KB Output is correct
8 Correct 54 ms 7036 KB Output is correct
9 Correct 54 ms 7372 KB Output is correct
10 Correct 52 ms 7368 KB Output is correct
11 Correct 47 ms 7284 KB Output is correct
12 Incorrect 18 ms 5084 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 36.0

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