oj.uz

Submission #59869

# Submission time Handle Problem Language Result Execution time Memory
59869 2018-07-23T08:18:56 Z 강태규(#1723) Cultivation (JOI17_cultivation) C++11
0 / 100
 13 ms 524 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const llong inf = 1e12;
int r, c, n;
int x[301];
int y[301];

void compress(vector<int> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

struct evt {
    int x, y, t;
    bool operator<(const evt &p) const {
        return x < p.x;
    }
};

llong solve2(int u, int d) {
    llong ret = 0;
    vector<evt> ev;
    for (int i = 1; i <= n; ++i) {
        ev.push_back({ max(x[i] - u, 1), y[i], 0 });
        ev.push_back({ min(x[i] + d, r) + 1, y[i], 1 });
    }
    sort(ev.begin(), ev.end());
    
    multiset<int> mp;
    int pr = 1;
    for (evt i : ev) {
        if (pr < i.x) {
            if (mp.empty()) return inf;
            pr = 0;
            for (int i : mp) {
                ret = max(ret, (llong)i - pr - 1);
                pr = i;
            }
            ret = max(ret, (llong)c - pr);
            pr = i.x;
        }
        if (r < i.x) break;
        if (i.t) mp.erase(mp.find(i.y));
        else mp.insert(i.y);
    }
    return ret;
}

int main() {
    scanf("%d%d%d", &r, &c, &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", x + i, y + i);
    }
    if (r > 40 && n > 30) return 0;
    llong ans = inf;
    vector<int> dc;
    for (int i = 1; i <= n; ++i) {
        dc.push_back(r - x[i]);
    }
    compress(dc);
    for (int i : dc) {
        x[0] = -i;
        vector<int> udc;
        for (int j = 0; j <= n; ++j) {
            for (int k = j; k <= n; ++k) {
                int a = x[k] - x[j];
                if (a < 0) a = -a;
                udc.push_back(a);
                if (a) udc.push_back(a - 1);
            }
        }
        compress(udc);
        for (int j : udc) {
            if (j < i) continue;
            ans = min(ans, solve2(j - i, i) + j);
        }
    }
    printf("%lld\n", ans);
	return 0;
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &r, &c, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", x + i, y + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 4 ms 524 KB Output is correct
5 Incorrect 3 ms 524 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 4 ms 524 KB Output is correct
5 Incorrect 3 ms 524 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 4 ms 524 KB Output is correct
5 Incorrect 3 ms 524 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 4 ms 524 KB Output is correct
5 Incorrect 3 ms 524 KB Output isn't correct
6 Halted 0 ms 0 KB -