제출 #399900

#제출 시각아이디문제언어결과실행 시간메모리
399900dualityCultivation (JOI17_cultivation)C++11
0 / 100
2 ms204 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- int S[300],E[300]; vi vv; vector<pair<pii,int> > vv2; multiset<int> SS; int main() { int i; int R,C,N; scanf("%d %d %d",&R,&C,&N); for (i = 0; i < N; i++) scanf("%d %d",&S[i],&E[i]),S[i]--,E[i]--; int j,k; int ans = 2e9; for (i = 0; i < N; i++) { int u = S[i]; vv.pb(0),vv.pb(R-1); for (j = 0; j < N; j++) vv.pb(max(S[j]-u-1,0)); sort(vv.begin(),vv.end()); vv.resize(unique(vv.begin(),vv.end())-vv.begin()); for (j = 0; j < vv.size(); j++) { vpii v; for (k = 0; k < N; k++) { if ((vv[j] >= S[k]-u) && (vv[j] <= S[k])) v.pb(mp(0,E[k])); else if (vv[j] > S[k]) v.pb(mp(vv[j]-S[k],E[k])); } sort(v.begin(),v.end()); for (k = 0; k < v.size(); k++) SS.insert(v[k].second); int l = *SS.begin(),r = C-*SS.rbegin()-1,lr = 0; for (auto it = SS.begin(); it != SS.end(); it++) { auto it2 = it; it2++; if (it2 != SS.end()) lr = max(lr,*it2-*it-1); } vv2.pb(mp(mp(R,l),0)),vv2.pb(mp(mp(R,r),1)),vv2.pb(mp(mp(R,lr),2)); for (k = v.size()-1; k >= 0; k--) { auto it = SS.find(v[k].second); it = SS.erase(it); auto it2 = it; if (it2 == SS.begin()) l = max(l,*it); else it2--; if (it == SS.end()) r = max(R,C-*it2-1); else lr = max(lr,*it-*it2-1); vv2.pb(mp(mp(v[k].first-1,l),0)),vv2.pb(mp(mp(v[k].first-1,r),1)),vv2.pb(mp(mp(v[k].first-1,lr),2)); } } int l = 0,r = 0,lr = 0; sort(vv2.begin(),vv2.end()); for (j = vv2.size()-1; j >= 0; j--) { if (vv2[j].first.first < R) ans = min(ans,u+vv2[j].first.first+1+max(l+r,lr)); if (vv2[j].second == 0) l = max(l,vv2[j].first.second); else if (vv2[j].second == 1) r = max(r,vv2[j].first.second); else lr = max(lr,vv2[j].first.second); } vv.clear(),vv2.clear(); } printf("%d\n",ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

cultivation.cpp: In function 'int main()':
cultivation.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (j = 0; j < vv.size(); j++) {
      |                     ~~^~~~~~~~~~~
cultivation.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (k = 0; k < v.size(); k++) SS.insert(v[k].second);
      |                         ~~^~~~~~~~~~
cultivation.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%d %d %d",&R,&C,&N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:66:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     for (i = 0; i < N; i++) scanf("%d %d",&S[i],&E[i]),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...