oj.uz

Submission #989732

# Submission time Handle Problem Language Result Execution time Memory
989732 2024-05-28T16:43:28 Z samek08 Potatoes and fertilizers (LMIO19_bulves) C++14
0 / 100
 37 ms 67668 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) 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
0 / 24.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 5 ms 14040 KB Output is correct
5 Correct 12 ms 21896 KB Output is correct
6 Incorrect 37 ms 67668 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 8540 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Incorrect 1 ms 8956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

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