Submission #168693

#TimeUsernameProblemLanguageResultExecution timeMemory
168693ho94949Cultivation (JOI17_cultivation)C++17
5 / 100
3 ms1140 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 303, INF = 0x3f3f3f3f; int R, C, N, S[MAXN], E[MAXN]; int key[MAXN]; vector<int> val[MAXN]; int main() { scanf("%d%d%d", &R, &C, &N); map<int, vector<int> > pts; for(int i=0; i<N; ++i) { scanf("%d%d", S+i, E+i); pts[E[i]].push_back(S[i]); } int K = 0; for(auto [a, b]: pts) { key[K] = a; val[K] = b; ++K; } auto ins = [](vector<int> &V, int x) { V.push_back(x); for(int i=(int)V.size()-1; i>0; --i) { if(V[i] < V[i-1]) swap(V[i], V[i-1]); else break; } }; auto m2 = [](vector<tuple<int, int, int, int> > merged, vector<tuple<int, int, int, int> > abc) { //merge merged, abc vector<tuple<int, int, int, int> > newmerged; size_t tp1 = 0, tp2 = 0; while(tp1 != merged.size() || tp2 != abc.size()) { int n1 = tp1==merged.size()?INF:get<0>(merged[tp1]); int n2 = tp2==abc.size()?INF:get<0>(abc[tp2]); if(n1 < n2) { auto [_n1, a1, b1, c1] = merged[tp1]; auto [_n2, a2, b2, c2] = abc[tp2-1]; newmerged.emplace_back(n1, max(a1, a2), max(b1, b2), max(c1, c2)); ++tp1; } else if(n1 > n2) { auto [_n1, a1, b1, c1] = merged[tp1-1]; auto [_n2, a2, b2, c2] = abc[tp2]; newmerged.emplace_back(n2, max(a1, a2), max(b1, b2), max(c1, c2)); ++tp2; } else { auto [_n1, a1, b1, c1] = merged[tp1]; auto [_n2, a2, b2, c2] = abc[tp2]; newmerged.emplace_back(n1, max(a1, a2), max(b1, b2), max(c1, c2)); ++tp1; ++tp2; } } return newmerged; }; int rans = 2*INF; vector<tuple<int, int, int, int> > merged; merged.emplace_back(0, 0, 0, 0); for(int i=K-1; i>=0; --i) { vector<int> V; vector<tuple<int, int, int, int> > abc; for(int j=K-1; j>=0; --j) { for(auto x: val[j]) ins(V, x); int n = C-key[j] + key[i] - 1; //moved key[i]-1 west time int a = V[0]-1, b = R-V.back(), c = INF; for(int k=0; k<(int)V.size()-1; ++k) if(V[k] != V[k+1]) c = min(c, V[k+1]-V[k]-1); if(V[0] == V.back()) c = 0; if(abc.size() == 0 && n != 0) abc.emplace_back(0, INF, INF, INF); abc.emplace_back(n, a, b, c); } vector<tuple<int, int, int, int> > mm = m2(merged, abc); for(auto x: mm) { auto [a, b, c, d] = x; int ans = a + max(d, b+c); rans = min(ans, rans); //cout << a << " " << b << " " << c <<" " <<d <<endl; } if(i == 0) break; V.clear(); abc.clear(); for(int j=i-1; j>=0; --j) { for(auto x: val[j]) ins(V, x); int n = key[i] - key[j] - 1; int a = V[0]-1, b = R-V.back(), c = a+b; for(int k=0; k<(int)V.size()-1; ++k) c = min(c, V[k+1]-V[k]); if(abc.size() == 0 && n != 0) abc.emplace_back(0, INF, INF, INF); abc.emplace_back(n, a, b, c); } merged = m2(merged, abc); } printf("%d\n", rans); }

Compilation message (stderr)

cultivation.cpp: In lambda function:
cultivation.cpp:49:38: warning: unused variable '_n1' [-Wunused-variable]
                 auto [_n1, a1, b1, c1] = merged[tp1];
                                      ^
cultivation.cpp:50:38: warning: unused variable '_n2' [-Wunused-variable]
                 auto [_n2, a2, b2, c2] = abc[tp2-1];
                                      ^
cultivation.cpp:56:38: warning: unused variable '_n1' [-Wunused-variable]
                 auto [_n1, a1, b1, c1] = merged[tp1-1];
                                      ^
cultivation.cpp:57:38: warning: unused variable '_n2' [-Wunused-variable]
                 auto [_n2, a2, b2, c2] = abc[tp2];
                                      ^
cultivation.cpp:63:38: warning: unused variable '_n1' [-Wunused-variable]
                 auto [_n1, a1, b1, c1] = merged[tp1];
                                      ^
cultivation.cpp:64:38: warning: unused variable '_n2' [-Wunused-variable]
                 auto [_n2, a2, b2, c2] = abc[tp2];
                                      ^
cultivation.cpp: In function 'int main()':
cultivation.cpp:11: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:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", S+i, E+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...