oj.uz

Submission #989735

# Submission time Handle Problem Language Result Execution time Memory
989735 2024-05-28T16:49:52 Z samek08 Potatoes and fertilizers (LMIO19_bulves) C++14
24 / 100
 92 ms 65372 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int MAXN = 5e5+5, INF = 1e9+50;
const ll INF_L = (ll)1e18+(ll)50000;

int n;
int A[MAXN];
int B[MAXN];
int C[MAXN];
ll S[MAXN];
ll G[MAXN];
vector<ll> stan;
vector<vector<ll>> dp;

void solve()
{
	cin >> n;
	rep(i,n) cin >> A[i] >> B[i];

	rep(i,n) C[i] = A[i]-B[i];

	S[0] = C[0];
	for(int i = 1; i < n; ++i) S[i] = S[i-1] + C[i];

	set<ll> fg;
	rep(i,n)
	{
		if(S[i] >= 0 and S[i] <= S[n-1]) fg.insert(S[i]);
	}
	for(auto it = fg.begin(); it != fg.end(); ++it) stan.pb(*it);

	dp.assign(n,{});
	rep(i,n) dp[i].assign((int)stan.size(),INF_L);

	//rep(i,n) cout << S[i] << endl;

	rep(i,n)
	{
		ll mn = INF_L;
		rep(j,(int)stan.size())
		{
			if(i > 0) mn = min(mn,dp[i-1][j]);
			/*if((i == 0 and S[i] > stan[j]) or (i == n-1 and S[i] < stan[j]))
			{
				dp[i][j] = INF_L;
				continue;
			}*/
			dp[i][j] = abs(S[i]-stan[j]);
			if(i > 0)
			{
				if(mn == INF_L) dp[i][j] = INF_L;
				else dp[i][j] += mn;
			}
		}
	}

	/*rep(i,n)
	{
		rep(j,(int)stan.size()) cout << dp[i][j] << ' ';
		cout << '\n';
	}*/

	ll mn = INF_L;
	rep(i,(int)stan.size()) mn = min(mn,dp[n-1][i]);
	cout << mn << '\n';
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//cin >> T;
	while(T--) solve();

	return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 7 ms 10012 KB Output is correct
5 Correct 13 ms 15180 KB Output is correct
6 Correct 39 ms 25668 KB Output is correct
7 Correct 84 ms 44368 KB Output is correct
8 Correct 74 ms 42432 KB Output is correct
9 Correct 92 ms 43348 KB Output is correct
10 Correct 55 ms 39504 KB Output is correct
11 Correct 55 ms 41044 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 7 ms 10012 KB Output is correct
5 Correct 13 ms 15180 KB Output is correct
6 Correct 39 ms 25668 KB Output is correct
7 Correct 84 ms 44368 KB Output is correct
8 Correct 74 ms 42432 KB Output is correct
9 Correct 92 ms 43348 KB Output is correct
10 Correct 55 ms 39504 KB Output is correct
11 Correct 55 ms 41044 KB Output is correct
12 Incorrect 20 ms 15944 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 6492 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 7 ms 19804 KB Output is correct
6 Incorrect 33 ms 65372 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 7 ms 19804 KB Output is correct
7 Incorrect 33 ms 65372 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 7 ms 19804 KB Output is correct
7 Incorrect 33 ms 65372 KB Output isn't correct
8 Halted 0 ms 0 KB -