제출 #77590

#제출 시각아이디문제언어결과실행 시간메모리
77590dualityBuilding Bridges (CEOI17_building)C++11
30 / 100
88 ms2656 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 h[100000]; LLI w[100001],dp[100000]; struct line { LLI m,b; }; bool comp(line a,line b) { if (a.m == b.m) return a.b < b.b; else return a.m > b.m; } int bad(line a,line b,line c) { return (long double) (b.b-a.b)*(b.m-c.m) >= (long double) (b.b-c.b)*(b.m-a.m); } vector<line> v1,v2; int main() { int i; int n; scanf("%d",&n); for (i = 0; i < n; i++) scanf("%d",&h[i]); for (i = 0; i < n; i++) scanf("%lld",&w[i+1]),w[i+1] += w[i]; int j,s = sqrt(n)+EPS; v1.pb((line){-2*h[0],(LLI) h[0]*h[0]-w[1]}); for (i = 1; i < n; i++) { int l = 0,r = v1.size()-1; while (l < r) { int m = (l+r) / 2; if (v1[m].m*h[i]+v1[m].b < v1[m+1].m*h[i]+v1[m+1].b) r = m; else l = m+1; } dp[i] = (LLI) h[i]*h[i]+w[i]+v1[l].m*h[i]+v1[l].b; for (j = 0; j < v2.size(); j++) dp[i] = min(dp[i],(LLI) h[i]*h[i]+w[i]+v2[j].m*h[i]+v2[j].b); v2.pb((line){-2*h[i],(LLI) h[i]*h[i]-w[i+1]+dp[i]}); if (v2.size() > s) { vector<line> temp(v1.size()+v2.size()); sort(v2.begin(),v2.end(),comp); merge(v1.begin(),v1.end(),v2.begin(),v2.end(),temp.begin(),comp); v1.clear(),v2.clear(); for (j = 0; j < temp.size(); j++) { if (!v1.empty() && (temp[j].m == v1.back().m)) continue; while (!v1.empty() && bad(v1[v1.size()-2],v1.back(),temp[j])) v1.pop_back(); v1.pb(temp[j]); } } } printf("%lld\n",dp[n-1]); return 0; }

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

building.cpp: In function 'int main()':
building.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < v2.size(); j++) dp[i] = min(dp[i],(LLI) h[i]*h[i]+w[i]+v2[j].m*h[i]+v2[j].b);
                     ~~^~~~~~~~~~~
building.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (v2.size() > s) {
             ~~~~~~~~~~^~~
building.cpp:93:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < temp.size(); j++) {
                         ~~^~~~~~~~~~~~~
building.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
building.cpp:73:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < n; i++) scanf("%d",&h[i]);
                             ~~~~~^~~~~~~~~~~~
building.cpp:74:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < n; i++) scanf("%lld",&w[i+1]),w[i+1] += w[i];
                             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...