Submission #55271

#TimeUsernameProblemLanguageResultExecution timeMemory
55271ksun48Cultivation (JOI17_cultivation)C++14
30 / 100
1075 ms1284 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL;; LL r, c, n; vector<pair<LL,LL> > seeds; const LL INF = 3100100100; LL best = INF; set<pair<LL,LL> > tried; void tryx(LL x, LL startx){ if(x < 0 || tried.find({x,startx}) != tried.end()){ return; } tried.insert({x,startx}); vector<LL> stuff[r + x]; for(pair<LL,LL> z : seeds){ for(LL j = 0; j <= x; j++){ stuff[j + z.first].push_back(z.second); } } vector<LL> up(r+x, 0); vector<LL> down(r+x, 0); vector<LL> tot(r+x, 0); for(LL j = 0; j < r+x; j++){ vector<LL> grass = stuff[j]; sort(grass.begin(), grass.end()); if(grass.size() == 0){ up[j] = down[j] = tot[j] = INF; } else { up[j] = grass[0] - 0; down[j] = c-1 - grass[grass.size()-1]; for(LL i = 0; i + 1 < grass.size(); i++){ tot[j] = max(tot[j], grass[i+1] - grass[i] - 1); } } } LL maxup = 0; LL maxdown = 0; LL maxtot = 0; for(LL i = startx; i < startx + r; i++){ maxup = max(maxup, up[i]); maxdown = max(maxdown, down[i]); maxtot = max(maxtot, tot[i]); } best = min(best, max(maxup + maxdown, maxtot) + x); } int main(){ cin >> r >> c >> n; for(LL i = 0; i < n; i++){ LL s, e; cin >> s >> e; s--; e--; seeds.push_back({s,e}); } sort(seeds.begin(), seeds.end()); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ tryx(seeds[i].first + r-1 - seeds[j].first, seeds[i].first); } } cout << best << '\n'; }

Compilation message (stderr)

cultivation.cpp: In function 'void tryx(LL, LL)':
cultivation.cpp:32:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(LL i = 0; i + 1 < grass.size(); i++){
                  ~~~~~~^~~~~~~~~~~~~~
#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...