oj.uz

Submission #1036594

# Submission time Handle Problem Language Result Execution time Memory
1036594 2024-07-27T14:36:12 Z Misha_Yuzvik Bulldozer (JOI17_bulldozer) C++14
0 / 100
 16 ms 988 KB 
# include <bits/stdc++.h>
using namespace std;
# define For(i , l , r) for(int i = (l); i <= (r); i++)
# define Rep(i , n) For(i , 0 , (n) - 1)
# define size(x) (long long)x.size()
# define MAXN 2005
# define MAXK 1000005
# define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll inf = 1e9 + 7;
const ll mod = 1e9 + 9;
const ld eps = 0.000000001;
ll n , m , k , ans = 0 , q;
struct pt {
   ll x , y , val;
   bool operator == (const pt& p) {
       return (p.x == x && p.y == y);
   }
};
struct vc {
    ll x , y;
    ll nom1 , nom2;
};
ll cross_pr(const vc &a , const vc& b) {
    return a.x * b.y - b.x * a.y;
}
struct node {
    ll sum , wyn , mxp , mxs;
};
vector<node>t;
ll sz = 1;
void init(ll n) {
    while (sz < n) sz *= 2;
    t.resize(sz * 2 + 5);
}
node calc(node &left , node &right) {
     node cur = {0 , 0 , 0 , 0};
     cur.sum = left.sum + right.sum;
     cur.mxp = max(left.mxp , left.sum + right.mxp);
     cur.mxs = max(right.mxs , right.sum + left.mxs);
     cur.wyn = max({left.wyn , right.wyn , left.mxs + right.mxp});
     return cur;
}
void upd(ll nom , ll val , ll x , ll lx , ll rx) {
       if (rx - lx == 1) {
            t[x].sum = val;
            t[x].mxp = t[x].mxs = t[x].wyn = max(0LL , val);
            return;
       }
       ll mid = (lx + rx) / 2;
       if (nom < mid) upd(nom , val , (x << 1) , lx , mid);
       else upd(nom , val , (x << 1) + 1 , mid , rx);
       t[x] = calc(t[x << 1] , t[(x << 1) + 1]);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    vector<pt>p(n);
    for (auto &[x , y , val] : p) cin >> x >> y >> val;
    sort(p.begin() , p.end() , 
         [](const auto& l , const auto& r) {
             if (l.x == r.x) return l.y > r.y;
             return l.x < r.x;   
         });
    vector<vc>l;
    Rep (i , n) {
        For (j , i + 1 , n - 1) {
            l.push_back({p[i].x - p[j].x , p[i].y - p[j].y , i , j});  
            if (l.back().x == 0) l.pop_back();
            if (l.back().x < 0) l.back().x *= -1 , l.back().y *= -1;
        }
    }
    sort(all(l) , 
       [&](const auto& l , const auto& r) {
              ll f = cross_pr(l , r);
              if (f == 0) {
                  if (p[l.nom1] == p[r.nom1]) return p[l.nom2].x < p[r.nom2].x;
                  else return p[l.nom1].x < p[l.nom2].x;
              }
              return f < 0;
    });
    init(n);
    Rep (i , n) {
        upd(i , p[i].val , 1 , 0 , sz);
    }
    vector<ll>pos(n);
    Rep (i , n) pos[i] = i;
    ld prev_tg = (ld)l[0].y / (ld)l[0].x;
    ans = t[1].wyn;
    Rep (i , size(l)) {
          ll x = l[i].x , y = l[i].y , nom1 = l[i].nom1 , nom2 = l[i].nom2;
          if ((ld)y / (ld)x != prev_tg) {
            ll cur_res = t[1].wyn;
            ans = max(ans , cur_res);
            prev_tg = (ld)y / (ld)x;
          }
          swap(pos[nom1] , pos[nom2]);
          ll pos1 = pos[nom1] , pos2 = pos[nom2];
          upd(pos1 , p[nom1].val , 1 , 0 , sz);
          upd(pos2 , p[nom2].val , 1 , 0 , sz);
          
    }
    ans = max(ans , t[1].wyn);
    cout << ans;
}
/*

*/

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:61:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for (auto &[x , y , val] : p) cin >> x >> y >> val;
      |                ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 732 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 732 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Runtime error 1 ms 348 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 732 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 732 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Runtime error 1 ms 348 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 732 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 732 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 2 ms 732 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Runtime error 1 ms 348 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -