oj.uz

답안 #262546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
262546 2020-08-13T03:39:42 Z fivefourthreeone Bulldozer (JOI17_bulldozer) C++17
0 / 100
 84 ms 896 KB 
//#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;
}

Compilation message

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()) {
      |         ^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 896 KB Output is correct
2 Correct 74 ms 896 KB Output is correct
3 Correct 73 ms 896 KB Output is correct
4 Correct 76 ms 896 KB Output is correct
5 Correct 73 ms 896 KB Output is correct
6 Correct 75 ms 896 KB Output is correct
7 Correct 73 ms 896 KB Output is correct
8 Correct 84 ms 896 KB Output is correct
9 Correct 75 ms 896 KB Output is correct
10 Correct 77 ms 896 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 896 KB Output is correct
2 Correct 74 ms 896 KB Output is correct
3 Correct 73 ms 896 KB Output is correct
4 Correct 76 ms 896 KB Output is correct
5 Correct 73 ms 896 KB Output is correct
6 Correct 75 ms 896 KB Output is correct
7 Correct 73 ms 896 KB Output is correct
8 Correct 84 ms 896 KB Output is correct
9 Correct 75 ms 896 KB Output is correct
10 Correct 77 ms 896 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -