Submission #843757

#	Time	Username	Problem	Language	Result	Execution time	Memory
843757		Mirali7	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	1020 ms	262144 KiB

bulves

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36