oj.uz

Submission #989740

# Submission time Handle Problem Language Result Execution time Memory
989740 2024-05-28T17:09:30 Z samek08 Potatoes and fertilizers (LMIO19_bulves) C++14
64 / 100
 125 ms 262144 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];
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];

	//rep(i,n) cin >> C[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]);
	}
	fg.insert(0);
	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] << ' ';
	//cout << '\n';

	rep(i,n)
	{
		ll mn = INF_L;
		rep(j,(int)stan.size())
		{
			if(i > 0) mn = min(mn,dp[i-1][j]);
			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 0 ms 348 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 7 ms 4436 KB Output is correct
5 Correct 14 ms 8540 KB Output is correct
6 Correct 39 ms 22344 KB Output is correct
7 Correct 80 ms 44220 KB Output is correct
8 Correct 72 ms 42576 KB Output is correct
9 Correct 79 ms 41808 KB Output is correct
10 Correct 60 ms 39372 KB Output is correct
11 Correct 58 ms 39436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 7 ms 4436 KB Output is correct
5 Correct 14 ms 8540 KB Output is correct
6 Correct 39 ms 22344 KB Output is correct
7 Correct 80 ms 44220 KB Output is correct
8 Correct 72 ms 42576 KB Output is correct
9 Correct 79 ms 41808 KB Output is correct
10 Correct 60 ms 39372 KB Output is correct
11 Correct 58 ms 39436 KB Output is correct
12 Correct 28 ms 11244 KB Output is correct
13 Correct 52 ms 26676 KB Output is correct
14 Correct 85 ms 44320 KB Output is correct
15 Correct 70 ms 42324 KB Output is correct
16 Correct 70 ms 41808 KB Output is correct
17 Correct 61 ms 39508 KB Output is correct
18 Correct 1 ms 604 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 6 ms 11732 KB Output is correct
7 Correct 33 ms 59448 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 7 ms 12380 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 6 ms 11732 KB Output is correct
7 Correct 33 ms 59448 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 7 ms 12380 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 17 ms 31324 KB Output is correct
13 Correct 37 ms 69200 KB Output is correct
14 Correct 41 ms 70944 KB Output is correct
15 Correct 40 ms 71300 KB Output is correct
16 Correct 17 ms 19292 KB Output is correct
17 Correct 16 ms 27028 KB Output is correct
18 Correct 12 ms 21340 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 6 ms 11732 KB Output is correct
7 Correct 33 ms 59448 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 7 ms 12380 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 7 ms 4436 KB Output is correct
12 Correct 14 ms 8540 KB Output is correct
13 Correct 39 ms 22344 KB Output is correct
14 Correct 80 ms 44220 KB Output is correct
15 Correct 72 ms 42576 KB Output is correct
16 Correct 79 ms 41808 KB Output is correct
17 Correct 60 ms 39372 KB Output is correct
18 Correct 58 ms 39436 KB Output is correct
19 Correct 28 ms 11244 KB Output is correct
20 Correct 52 ms 26676 KB Output is correct
21 Correct 85 ms 44320 KB Output is correct
22 Correct 70 ms 42324 KB Output is correct
23 Correct 70 ms 41808 KB Output is correct
24 Correct 61 ms 39508 KB Output is correct
25 Correct 17 ms 31324 KB Output is correct
26 Correct 37 ms 69200 KB Output is correct
27 Correct 41 ms 70944 KB Output is correct
28 Correct 40 ms 71300 KB Output is correct
29 Correct 17 ms 19292 KB Output is correct
30 Correct 16 ms 27028 KB Output is correct
31 Correct 12 ms 21340 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Runtime error 125 ms 262144 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -