Submission #999691

#TimeUsernameProblemLanguageResultExecution timeMemory
999691TobCultivation (JOI17_cultivation)C++14
0 / 100
2 ms2140 KiB
#include <bits/stdc++.h> #define F first #define S second #define all(x) x.begin(), x.end() #define pb push_back #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef long long ll; typedef pair <int, int> pii; const int N = 307, inf = 2e9; int n, m, k; int a[N], b[N]; int mem[2*N][N]; vector <int> add[2*N], rem[2*N]; int main () { FIO; cin >> n >> m >> k; vector <pii> so; for (int i = 0; i < k; i++) { cin >> a[i] >> b[i]; a[i]--; b[i]--; so.pb({a[i], b[i]}); } sort(all(so)); for (int i = 0; i < k; i++) { a[i] = so[i].F; b[i] = so[i].S; } vector <int> v, po; int d = a[0]; for (int i = 0; i < k; i++) a[i] -= d; d = n-a[k-1]-1; for (int i = 1; i < k; i++) d = max(d, a[i]-a[i-1]-1); for (int i = 0; i < k; i++) { for (int j = i; j < k; j++) { if (a[j]-a[i] >= d) v.pb(a[j]-a[i]); if (a[j]-a[i]-1 >= d) v.pb(a[j]-a[i]-1); } if (n-a[i]-1 >= d) v.pb(n-a[i]-1); } v.pb(d); sort(all(v)); v.erase(unique(all(v)), v.end()); for (int i = 0; i < k; i++) { if (a[i]) po.pb(a[i]-1); po.pb(a[i]); } po.pb(m-1); sort(all(po)); po.erase(unique(all(po)), po.end()); for (int i = 0; i < 2*N; i++) for (int j = 0; j < N; j++) mem[i][j] = inf; for (int i = 0; i < po.size(); i++) { set <int> s; multiset <int> rj; int o = k-1; for (int j = 0; j < k; j++) if (a[j] > po[i]) { o = j-1; break; } #define EDGE() {(*s.begin() + m - *s.rbegin() - 1)} for (int j = o; j >= 0; j--) { mem[i][j] = mem[i][j+1]; if (s.find(b[j]) != s.end()) continue; auto p1 = s.lower_bound(b[j]); if (p1 == s.end()) { if (!s.empty()) { rj.erase(rj.find(EDGE())); rj.insert(b[j]-*s.rbegin()-1); } s.insert(b[j]); rj.insert(EDGE()); } else if (p1 == s.begin()) { rj.erase(rj.find(EDGE())); rj.insert(*s.begin()-b[j]-1); s.insert(b[j]); rj.insert(EDGE()); } else { int x = *p1 - b[j] - 1; auto p2 = p1; --p2; int y = b[j] - *p2 - 1; rj.erase(rj.find(x+y+1)); rj.insert(x); rj.insert(y); } mem[i][j] = *rj.rbegin(); } } int mn = inf; for (auto x : v) { for (int i = 0, j = 0; i < k; i++) { while (j < po.size() && po[j] < a[i]) j++; add[j].pb(i); } for (int i = 0, j = 0; i < k; i++) { while (j < po.size() && po[j] < a[i]+x) j++; rem[j].pb(i); } queue <int> q; int mx = 0; for (int i = 0; i < po.size(); i++) { for (auto y : add[i]) q.push(y); mx = max(mx, mem[i][q.front()]); for (auto y : rem[i]) q.pop(); add[i].clear(); rem[i].clear(); } mn = min(mn, mx+x); } cout << mn << "\n"; return 0; }

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < po.size(); i++) {
      |                  ~~^~~~~~~~~~~
cultivation.cpp:101:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    while (j < po.size() && po[j] < a[i]) j++;
      |           ~~^~~~~~~~~~~
cultivation.cpp:105:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    while (j < po.size() && po[j] < a[i]+x) j++;
      |           ~~^~~~~~~~~~~
cultivation.cpp:110:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for (int i = 0; i < po.size(); i++) {
      |                   ~~^~~~~~~~~~~
cultivation.cpp:113:14: warning: unused variable 'y' [-Wunused-variable]
  113 |    for (auto y : rem[i]) q.pop();
      |              ^
#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...