oj.uz

Submission #154608

# Submission time Handle Problem Language Result Execution time Memory
154608 2019-09-23T10:04:32 Z Mercenary Bulldozer (JOI17_bulldozer) C++14
0 / 100
 4 ms 628 KB 
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;

const int maxn = 2e3 + 5;

int n;
struct point{
    int x , y , c;
}a[maxn];
struct line{
    int x , y , ii , jj;
};
struct node{
    ll res , pre , sum , suf;
    node(){};
    node(ll sum , ll res , ll pre , ll suf):sum(sum) , res(res) , pre(pre) , suf(suf){}
    node operator + (const node & other){
        return node(
                sum + other.sum,
                max({res , other.res , suf + other.pre}),
                max({pre , sum + other.pre}),
                max({other.suf , other.sum + suf})
                    );
    }
}s[maxn * 4];

void Build(int x , int l , int r){
    if(l == r){
        s[x] = node(a[l].c , a[l].c , a[l].c , a[l].c);
        return;
    }
    int mid = l + r >> 1;
    Build(x * 2 , l , mid);
    Build(x * 2 + 1 , mid + 1 , r);
    s[x] = s[x * 2] + s[x * 2 + 1];
}

void update(int x , int l , int r , int pos , int val){
    if(l == r){
        s[x] = node(val , val , val ,val);
        return;
    }
    int mid = l + r >> 1;
    if(mid >= pos)update(x * 2 , l , mid , pos , val);
    else update(x * 2 + 1 , mid + 1 , r , pos , val);
    s[x] = s[x * 2] + s[x * 2 + 1];
}
int cur[maxn];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP", "r",stdin);
        freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i].x >> a[i].y >> a[i].c;
        cur[i] = i;
    }
    sort(a + 1 , a + n + 1 , [&](const point & x , const point & y){
            if(x.x == y.x)return x.y < y.y;
            return x.x < y.x;
         });
    vector<line> v;
    v.reserve(n * (n - 1) / 2);
    for(int i = 1 ; i <= n ; ++i){
        for(int j = i + 1 ; j <= n ; ++j){
            v.pb({a[i].x - a[j].x , a[i].y - a[j].y , i , j});
        }
    }
    stable_sort(v.begin(),v.end(),[&](const line & a , const line & b){
            return (ll)a.x * b.y - (ll)a.y * b.x > 0;
                });
    int j = 0;
    ll ans = 0;
    ans = max(0ll , s[1].res);
    for(int i = 0 ; i < (int)v.size() ; ){
        while(j < (int)v.size() && (ll)v[i].x * v[j].y == (ll)v[i].y * v[j].x){
            swap(cur[v[j].ii] , cur[v[j].jj]);
            update(1 , 1 , n , cur[v[j].ii] , a[v[j].ii].c);
            update(1 , 1 , n , cur[v[j].jj] , a[v[j].jj].c);
            ++j;
        }
        ans = max(ans , s[1].res);
        i = j;
    }
    cout << ans;
}

Compilation message

bulldozer.cpp: In constructor 'node::node(ll, ll, ll, ll)':
bulldozer.cpp:22:20: warning: 'node::sum' will be initialized after [-Wreorder]
     ll res , pre , sum , suf;
                    ^~~
bulldozer.cpp:22:8: warning:   'll node::res' [-Wreorder]
     ll res , pre , sum , suf;
        ^~~
bulldozer.cpp:24:5: warning:   when initialized here [-Wreorder]
     node(ll sum , ll res , ll pre , ll suf):sum(sum) , res(res) , pre(pre) , suf(suf){}
     ^~~~
bulldozer.cpp: In function 'void Build(int, int, int)':
bulldozer.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
bulldozer.cpp: In function 'void update(int, int, int, int, int)':
bulldozer.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 628 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Incorrect 3 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 628 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Incorrect 3 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 628 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Incorrect 3 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -