oj.uz

Submission #465215

# Submission time Handle Problem Language Result Execution time Memory
465215 2021-08-15T11:35:48 Z Vladth11 Bulldozer (JOI17_bulldozer) C++14
0 / 100
 1 ms 588 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 2001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;

int n;

class AINT{
public:
    struct Node{
        int st, dr, total;
        int ssm;
    };
    Node aint[NMAX * 4];
    Node combine(Node a, Node b){
        Node rez;
        rez.st = max({a.st, a.total + b.st, 0});
        rez.dr = max({b.dr, b.total + a.dr, 0});
        rez.total = a.total + b.total;
        rez.ssm = max({a.ssm, b.ssm, a.dr + b.st, 0}); ///hmmm
        return rez;
    }
    void update(int node, int st, int dr, int a, int b){
        if(st == dr){
          	//b = max(b, 0);
            aint[node] = {max(b, 0), max(0, b), b, max(0, b)};
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid){
            update(node * 2, st, mid, a, b);
        }else{
            update(node * 2 + 1, mid + 1, dr, a, b);
        }
        aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
    }
    Node best(){
        return aint[1];
    }
}st;

struct point{
    int x, y, val;
};

point v[NMAX], a[NMAX];
map <pii, int> mp;

struct event{
    pii p;
    double timp;
};

vector <event> events;

bool cmp(event a, event b){
    return a.timp < b.timp;
}

///De analizat
void swapElements(int a, int b){
    st.update(1, 1, n, mp[{v[a].x, v[a].y}], v[b].val);
    st.update(1, 1, n, mp[{v[b].x, v[b].y}], v[a].val);
    swap(mp[{v[b].x, v[b].y}], mp[{v[a].x, v[a].y}]);

}
///De analizat

bool cmpp(point a, point b){
    if(a.x != b.x)
        return a.x < b.x;
    return a.y > b.y;
}

void compute(int i, int j){
    events.push_back({{i, j}, (double)(v[i].y - v[j].y) / (double)(v[i].x - v[j].x)});
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> v[i].x >> v[i].y >> v[i].val;
    }
    sort(v + 1, v + n + 1, cmpp);
    for(i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            compute(i, j);
        }
    }
    for(i = 1; i <= n; i++){
        st.update(1, 1, n, i, v[i].val);
        mp[{v[i].x, v[i].y}] = i;
    }
    cout << st.best().ssm;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -