Submission #47682

#TimeUsernameProblemLanguageResultExecution timeMemory
47682maksim_gaponovCultivation (JOI17_cultivation)C++14
5 / 100
2074 ms748 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; void openFiles() { #ifdef KEK assert(freopen("input.txt", "r", stdin)); assert(freopen("output.txt", "w", stdout)); #endif } void IOoptimize() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } struct Action { int time; int l, r; int type; int id; }; bool operator< (const Action &a1, const Action &a2) { if (a1.time == a2.time) return a1.id < a2.id; return a1.time < a2.time; } struct Segment { int val; int cnt; int add; Segment() {} Segment(int val, int cnt, int add) : val(val), cnt(cnt), add(add) {} }; const int MAXN = 300; const int MAX = 40; int x[MAXN], y[MAXN]; Segment t[5 * MAX]; Segment merge(const Segment &s1, const Segment &s2) { if (s1.val < s2.val) return s1; if (s2.val < s1.val) return s2; Segment s3; s3.add = 0; s3.val = s1.val; s3.cnt = s1.cnt + s2.cnt; return s3; } void push(int x, int l, int r) { t[x].val += t[x].add; if (r - l > 1) { t[2 * x + 1].add += t[x].add; t[2 * x + 2].add += t[x].add; } t[x].add = 0; } void update(int x, int l, int r, int ql, int qr, int val) { push(x, l, r); if (l >= qr || r <= ql) return; if (ql <= l && r <= qr) { t[x].add += val; push(x, l, r); return; } int c = (l + r) / 2; update(2 * x + 1, l, c, ql, qr, val); update(2 * x + 2, c, r, ql, qr, val); t[x] = merge(t[2 * x + 1], t[2 * x + 2]); } Segment query(int x, int l, int r, int ql, int qr) { push(x, l, r); if (l >= qr || r <= ql) return Segment(INT_MAX, 0, 0); if (ql <= l && r <= qr) return t[x]; int c = (l + r) / 2; return merge( query(2 * x + 1, l, c, ql, qr), query(2 * x + 2, c, r, ql, qr) ); } int main() { openFiles(); IOoptimize(); int r, c; cin >> r >> c; int n; cin >> n; for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; x[i]--; y[i]--; } int ans = INT_MAX; int cnt[4]; for (cnt[0] = 0; cnt[0] <= MAX; cnt[0]++) for (cnt[1] = 0; cnt[1] <= MAX; cnt[1]++) for (cnt[2] = 0; cnt[2] <= MAX; cnt[2]++) for (cnt[3] = 0; cnt[3] <= MAX; cnt[3]++) { int new_ans = cnt[0] + cnt[1] + cnt[2] + cnt[3]; if (ans <= new_ans) continue; vector<Action> v; for (int i = 0; i < n; i++) { Action act; act.id = i; act.time = max(y[i] - cnt[1], 0); act.l = max(x[i] - cnt[0], 0); act.r = min(x[i] + cnt[2], r - 1); act.type = 1; v.push_back(act); act.time = min(y[i] + cnt[3] + 1, c); act.type = -1; v.push_back(act); } sort(v.begin(), v.end()); for (int i = 0; i < 5 * MAX; i++) { t[i].val = 0; t[i].cnt = 1; t[i].add = 0; } int last = 0; int sq = 0; for (auto act : v) { //cout << act.time << " " << act.l << " " << act.r << " " << act.type << "\n"; int active_count = 0; Segment seg = query(0, 0, r, 0, r); if (seg.val == 0) { active_count = r - seg.cnt; } else { active_count = r; } sq += active_count * (act.time - last); last = act.time; update(0, 0, r, act.l, act.r + 1, act.type); } //cout << sq << "\n"; //cout << "--/--\n"; if (sq == r * c) ans = new_ans; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...