oj.uz

Submission #843757

# Submission time Handle Problem Language Result Execution time Memory
843757 2023-09-04T14:13:40 Z Mirali7 Potatoes and fertilizers (LMIO19_bulves) C++17
0 / 100
 1000 ms 262144 KB 
#include <iostream>
#include <string>
#include <deque>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <fstream>
#include <stack>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <array>
#include <chrono>
#include <functional>
#include <numeric>
#include <complex>
using namespace std;

#define ll long long
#define ld long double
#define ull uint64_t
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pld pair<ld, ld>
#define fst first
#define snd second

#define forn(i, n) for (int i = 1; i <= n; i++)
#define dforn(i, a, b) for (int i = a; i <= b; i++) 
#define rforn(i, n) for (int i = n; i >= 1; i--)
#define rdforn(i, a, b) for (int i = b; i >= a; i--)
#define sforn(i, a, b, s) for (ll i = a; i <= b; i += s)
#define aforn(v, a) for (auto& v : a)
#define sz(a) ((int)a.size())

const int mod = 998244353;
const ld pi = acos(-1);
const ll N = 2e5 + 1;
const ll inf = 1e17;
const int iinf = 1 << 30;
const ld dinf = 1e14;
const double eps = 1e-14;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1), b(n + 1);
	ll sum = 0;
	vector<ll> pot;
	forn(i, n) {
		cin >> a[i] >> b[i];
		sum += b[i];
		forn(j, b[i]) {
			pot.push_back(i);
		}
	}
	vector<ll> dp(2 * sum + 1, inf);
	dp[sum] = 0;
	forn(i, n) {
		vector<ll> ndp(2 * sum + 1, inf);
		dforn(j, 0, 2 * sum) {
			dforn(h, 0, a[i]) {
				int nxt = j - b[i] + h;
				if (nxt < 0 || nxt > 2 * sum) {
					continue;
				}
				ndp[nxt] = min(ndp[nxt], dp[j] + abs(nxt - sum));
			}
		}
		dp = ndp;
	}
	ll ans = inf;
	dforn(i, sum, 2 * sum) {
		ans = min(ans, dp[i]);
	}
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.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 0 ms 348 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Runtime error 86 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Runtime error 86 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 254 ms 836 KB Output is correct
5 Execution timed out 1020 ms 1500 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Runtime error 86 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Runtime error 86 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -