제출 #262546

#제출 시각아이디문제언어결과실행 시간메모리
262546fivefourthreeoneBulldozer (JOI17_bulldozer)C++17
0 / 100
84 ms896 KiB
//#pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> #define owo(i,a, b) for(int i=(a);i<(b); ++i) #define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i) #define senpai push_back #define ttgl pair<int, int> #define ayaya cout<<"ayaya~"<<endl using namespace std; /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/ using ll = long long; using ld = long double; const ll MOD = 1000000007; const ll root = 62; int gcd(int a,int b){return b?gcd(b,a%b):a;} ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;} ll modInv(ll a){return binpow(a, MOD-2);} const double PI = acos(-1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int NINF = 0xc0c0c0c0; const ll INFLL = 0x3f3f3f3f3f3f3f3f; const ll NINFLL = 0xc0c0c0c0c0c0c0c0; const int mxN = 2001; int n; //0 = max_prefix; 1 = max_suffix; 2 = realmax; 3 = sum array<ll, 4> sgmax[2*mxN]; array<ll, 4> merge(array<ll, 4> a, array<ll, 4> b) { array<ll, 4> res = {0, 0, 0, 0}; res[0] = max(a[0], a[3] + b[0]); res[1] = max(b[1], b[3] + a[1]); res[2] = max({b[2], a[2], a[1] + b[0]}); res[3] = a[3] + b[3]; return res; } void upd(int p, ll val) { for(sgmax[p+=n] = {val, val, val, val}; p>1; p>>=1) { if(p&1) sgmax[p>>1] = merge(sgmax[p^1], sgmax[p]); else sgmax[p>>1] = merge(sgmax[p], sgmax[p^1]); } } array<ll, 4> qmax(int l, int r) { array<ll, 4> left = {0, 0, 0, 0}; array<ll, 4> right = {0, 0, 0, 0}; r++; for(l+=n, r+=n; l<r; l>>=1, r>>=1) { if(l&1) left = merge(left, sgmax[l++]); if(r&1) right = merge(sgmax[--r], right); } return merge(left, right); } struct event{ vector<array<int, 3>> points; int dx; int dy; int inter = 0; event(int x1, int y1, int x2, int y2, int a1, int a2) { points.senpai({x1, y1, a1}); points.senpai({x2, y2, a2}); int x = x2-x1; int y = y2-y1; int k = gcd(x, y); x/=k; y/=k; if(x<0||(x==0&&y<0)) { x = -x; y = -y; } dx = x; dy = y; //cout<<x<<" "<<y<<'\n'; if(x&&y) { inter = (-y1*dy)/dx + x1; }else if(x){ inter = y1; }else { inter = x1; } } bool operator<(const event &other) const{ if(dx*other.dy==dy*other.dx) { return inter<other.inter; } return dx*other.dy > dy*other.dx; } }; void comb(event &a, event &b) { if(a.points.size()<b.points.size())swap(a, b); for(auto p: b.points) { a.points.senpai(p); } sort(a.points.begin(), a.points.end()); a.points.resize(unique(a.points.begin(), a.points.end()) - a.points.begin()); } map<ttgl, int> mp; vector<event> all; array<int, 3> arr[mxN]; int main() { //freopen("file.in", "r", stdin); //freopen("file.out", "w", stdout); mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); cin.tie(0)->sync_with_stdio(0); cin>>n; owo(i, 0, n) { cin>>arr[i][0]>>arr[i][1]>>arr[i][2]; } owo(i, 0, n) { owo(j, i+1, n) { all.senpai(event(arr[i][0], arr[i][1], arr[j][0], arr[j][1], arr[i][2], arr[j][2])); //cout<<arr[i][0]<<" "<<arr[i][1]<<" "<<arr[j][0]<<" "<<arr[j][1]<<" "<<all[all.size()-1].inter<<"\n"; } } sort(all.begin(), all.end()); owo(i, 1, all.size()) { if(all[i-1].dx==all[i].dx&&all[i-1].dy==all[i].dy&&all[i].inter==all[i-1].inter) { comb(all[i-1], all[i]); all.erase(all.begin()+i); i--; } } for(auto e: all) { sort(e.points.begin(), e.points.end()); reverse(e.points.begin(), e.points.end()); } sort(arr, arr+n); owo(i, 0, n) { upd(i, arr[i][2]); mp[{arr[i][0], arr[i][1]}] = i; } //cout<<qmax(0, n-1)[2]<<"\n"; ll ans = 0; for(auto e: all) { //cout<<e.dx<<" "<<e.dy<<"\n"; vector<int> indicies; for(auto p: e.points) { indicies.senpai(mp[{p[0], p[1]}]); } sort(indicies.begin(), indicies.end()); owo(i, 0, indicies.size()) { //cout<<indicies[i]<<" "; upd(indicies[i], e.points[i][2]); mp[{e.points[i][0], e.points[i][1]}] = indicies[i]; } //cout<<"\n"; ans = max(ans, qmax(0, n-1)[2]); } cout<<ans<<"\n"; return 0; }

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

bulldozer.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
bulldozer.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define owo(i,a, b) for(int i=(a);i<(b); ++i)
      |                                    ^
bulldozer.cpp:119:5: note: in expansion of macro 'owo'
  119 |     owo(i, 1, all.size()) {
      |     ^~~
bulldozer.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define owo(i,a, b) for(int i=(a);i<(b); ++i)
      |                                    ^
bulldozer.cpp:144:9: note: in expansion of macro 'owo'
  144 |         owo(i, 0, indicies.size()) {
      |         ^~~
#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...