oj.uz

Submission #550656

# Submission time Handle Problem Language Result Execution time Memory
550656 2022-04-18T19:04:18 Z Lobo Cultivation (JOI17_cultivation) C++17
0 / 100
 110 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = -1;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int,int>> p;
    for(int i = 1; i <= q; i++) {
        int x,y; cin >> y >> x;
        p.pb(mp(x,y));
    }

    sort(all(p));

    int ans = inf;
    for(int up = 0; up <= n; up++) {
        for(int dw = 0; dw <= n; dw++) {
            vector<int> pos[n+10];
            for(auto X : p) {
                int x = X.fr;
                int y = X.sc;
                for(int i = max(1LL,y-dw); i <= min(n,y+up); i++) {
                    pos[i].pb(x);
                }
            }

            int sm = 0;
            int lmn = 0;
            int rmn = 0;
            for(int i = 1; i <= n; i++) {
                if(pos[i].size() == 0) {
                    sm = inf;
                    continue;
                }
                sort(all(pos[i]));
                lmn = max(lmn, pos[i][0]-1);
                rmn = max(rmn, n-pos[i].back());
                for(int j = 1; j < pos[i].size(); j++) {
                    sm = max(sm, pos[i][j]-pos[i][j-1]-1);
                }
            }
            ans = min(ans, dw+up+max(sm,lmn+rmn));
        }
    }

    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message

cultivation.cpp: In function 'void solve()':
cultivation.cpp:51:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for(int j = 1; j < pos[i].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -