oj.uz

Submission #169643

# Submission time Handle Problem Language Result Execution time Memory
169643 2019-12-21T18:55:37 Z mhy908 Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 66468 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=98765431298754321;
LL gcd(LL a, LL b){return b?gcd(b, a%b):a;}
struct Q{
    int buho;
    LL p, q;    //p/q
    bool operator<(const Q &b){
        if(buho!=b.buho)return buho<b.buho;
        if(buho>0)return p*b.q<b.p*q;
        return  p*b.q>b.p*q;
    }
    bool operator==(const Q &b){
        return buho==b.buho&&p==b.p&&q==b.q;
    }
};
int n;
pair<pll, int> point[2010];
vector<pair<Q, pii> > vc;
LL arr[2010];
int now[2010];
bool comp(pii a, pii b){
    if(a.F==b.F)return now[a.S]<now[b.S];
    return now[a.F]<now[b.F];
}
bool cmp(pair<Q, pii> a, pair<Q, pii> b){
    if(a.F==b.F)return a.S>b.S;
    return !(a.F<b.F);
}
bool cmp2(pair<pll, int> a, pair<pll, int> b){
    if(a.F.F==b.F.F)return a.F.S>b.F.S;
    return a.F.F<b.F.F;
}
struct SEGMENT_TREE {
    struct NODE {
        int st, fin;
        LL lmax, rmax, tmax, sum;
    } tree[15000];
    int x;
    void maketree(int point, int num) {
        if(num==1)tree[point].st=tree[point].fin=++x;
        if(num<=1)return;
        maketree(point*2, num-num/2);
        maketree(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void updaterange(int point, int num, LL p) {
        if(tree[point].st==tree[point].fin) {
            tree[point].lmax=p;
            tree[point].rmax=p;
            tree[point].tmax=p;
            tree[point].sum=p;
            return;
        }
        if(num<=tree[point*2].fin)updaterange(point*2, num, p);
        else updaterange(point*2+1, num, p);
        tree[point].lmax=max(tree[point*2].lmax, tree[point*2].sum+tree[point*2+1].lmax);
        tree[point].rmax=max(tree[point*2+1].rmax, tree[point*2+1].sum+tree[point*2].rmax);
        tree[point].sum=tree[point*2].sum+tree[point*2+1].sum;
        tree[point].tmax=max(max(tree[point*2].tmax, tree[point*2+1].tmax), max(tree[point*2].rmax+tree[point*2+1].lmax, max(tree[point].lmax, tree[point].rmax)));
    }
    LL ql(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].lmax;
        if(tree[point].st>b||tree[point].fin<a)return -llinf;
        return max(ql(point*2, a, b), qs(point*2, a, b)+ql(point*2+1, a, b));
    }
    LL qr(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].rmax;
        if(tree[point].st>b||tree[point].fin<a)return -llinf;
        return max(qr(point*2+1, a, b), qs(point*2+1, a, b)+qr(point*2, a, b));
    }
    LL qt(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].tmax;
        if(tree[point].st>b||tree[point].fin<a)return -llinf;
        return max(max(qt(point*2, a, b), qt(point*2+1, a, b)), max(qr(point*2, a, b)+ql(point*2+1, a, b), max(ql(point, a, b), qr(point, a, b))));
    }
    LL qs(int point, int a, int b){
        if(a>b)return 0;
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].sum;
        if(tree[point].st>b||tree[point].fin<a)return 0;
        return qs(point*2, a, b)+qs(point*2+1, a, b);
    }
    void update(int a, LL num) {
        updaterange(1, a, num);
    }
}seg;
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %lld", &point[i].F.F, &point[i].F.S, &arr[i]);
        point[i].S=i;
    }
    seg.maketree(1, n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<i; j++){
            LL tx=point[i].F.F-point[j].F.F;
            LL ty=point[i].F.S-point[j].F.S;
            if(tx==0)continue;
            Q temp;
            if(tx*ty>0)temp.buho=1;
            else if(tx*ty==0)temp.buho=0;
            else temp.buho=-1;
            LL gcdd=gcd(llabs(tx), llabs(ty));
            tx=llabs(tx)/gcdd;
            ty=llabs(ty)/gcdd;
            temp.p=ty;
            temp.q=tx;
            vc.pb(mp(temp, mp(j, i)));
        }
    }
    sort(point+1, point+n+1, cmp2);
    sort(vc.begin(), vc.end(), cmp);
    /*for(int i=0; i<vc.size(); i++){
        printf("%lld/%lld : %c <-> %c\n", vc[i].F.p, vc[i].F.q, 'A'-1+vc[i].S.F, 'A'-1+vc[i].S.S);
    }*/
    for(int i=1; i<=n; i++){
        seg.update(i, arr[point[i].S]);
        now[point[i].S]=i;
    }
    LL ans=max(0ll, seg.qt(1, 1, n));
    int pv=0;
    while(pv<vc.size()){
        vector<pii> tem;
        //puts("----");
        for(; pv<vc.size(); pv++){
            if(now[vc[pv].S.F]<now[vc[pv].S.S]){
                tem.pb(mp(vc[pv].S.F, vc[pv].S.S));
                //printf("swapping %c %c\n", 'A'-1+vc[pv].S.F, 'A'-1+vc[pv].S.S);
            }
            else{
                tem.pb(mp(vc[pv].S.S, vc[pv].S.F));
                //printf("swapping %c %c\n", 'A'-1+vc[pv].S.S, 'A'-1+vc[pv].S.F);
            }
            if(pv==vc.size()-1){
                pv++;
                break;
            }
            if(!(vc[pv].F==vc[pv+1].F)){
                pv++;
                break;
            }
        }
        sort(tem.begin(), tem.end(), comp);
        for(int j=0; j<tem.size(); j++){
            seg.update(now[tem[j].F], arr[tem[j].S]);
            seg.update(now[tem[j].S], arr[tem[j].F]);
            swap(now[tem[j].F], now[tem[j].S]);
        }
        /*for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(now[j]==i)printf("%c ", j+'A'-1);
            }
        }
        puts("");
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(now[j]==i)printf("%d ", arr[j]);
            }
        }
        puts("");*/
        LL temp=seg.qt(1, 1, n);
        //printf("ANS : %lld\n", temp);
        ans=max(ans, temp);
        //puts("----");
    }
    printf("%lld", ans);
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:134:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pv<vc.size()){
           ~~^~~~~~~~~~
bulldozer.cpp:137:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pv<vc.size(); pv++){
               ~~^~~~~~~~~~
bulldozer.cpp:146:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(pv==vc.size()-1){
                ~~^~~~~~~~~~~~~
bulldozer.cpp:156:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<tem.size(); j++){
                      ~^~~~~~~~~~~
bulldozer.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
bulldozer.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &point[i].F.F, &point[i].F.S, &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 760 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 7 ms 760 KB Output is correct
3 Correct 7 ms 760 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 7 ms 760 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 7 ms 760 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 6 ms 760 KB Output is correct
23 Correct 6 ms 760 KB Output is correct
24 Correct 6 ms 764 KB Output is correct
25 Correct 6 ms 760 KB Output is correct
26 Correct 6 ms 760 KB Output is correct
27 Correct 6 ms 760 KB Output is correct
28 Correct 6 ms 760 KB Output is correct
29 Correct 6 ms 760 KB Output is correct
30 Correct 6 ms 700 KB Output is correct
31 Correct 6 ms 760 KB Output is correct
32 Correct 6 ms 760 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 7 ms 760 KB Output is correct
3 Correct 7 ms 760 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 7 ms 760 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 7 ms 760 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 6 ms 760 KB Output is correct
23 Correct 6 ms 760 KB Output is correct
24 Correct 6 ms 764 KB Output is correct
25 Correct 6 ms 760 KB Output is correct
26 Correct 6 ms 760 KB Output is correct
27 Correct 6 ms 760 KB Output is correct
28 Correct 6 ms 760 KB Output is correct
29 Correct 6 ms 760 KB Output is correct
30 Correct 6 ms 700 KB Output is correct
31 Correct 6 ms 760 KB Output is correct
32 Correct 6 ms 760 KB Output is correct
33 Execution timed out 2040 ms 66468 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 7 ms 760 KB Output is correct
3 Correct 7 ms 760 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 7 ms 760 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 7 ms 760 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 6 ms 760 KB Output is correct
23 Correct 6 ms 760 KB Output is correct
24 Correct 6 ms 764 KB Output is correct
25 Correct 6 ms 760 KB Output is correct
26 Correct 6 ms 760 KB Output is correct
27 Correct 6 ms 760 KB Output is correct
28 Correct 6 ms 760 KB Output is correct
29 Correct 6 ms 760 KB Output is correct
30 Correct 6 ms 700 KB Output is correct
31 Correct 6 ms 760 KB Output is correct
32 Correct 6 ms 760 KB Output is correct
33 Execution timed out 2040 ms 66468 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 760 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 7 ms 760 KB Output is correct
17 Correct 7 ms 760 KB Output is correct
18 Correct 7 ms 760 KB Output is correct
19 Correct 7 ms 760 KB Output is correct
20 Correct 7 ms 760 KB Output is correct
21 Correct 7 ms 760 KB Output is correct
22 Correct 7 ms 760 KB Output is correct
23 Correct 7 ms 760 KB Output is correct
24 Correct 7 ms 760 KB Output is correct
25 Correct 7 ms 760 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 6 ms 760 KB Output is correct
37 Correct 6 ms 760 KB Output is correct
38 Correct 6 ms 760 KB Output is correct
39 Correct 6 ms 764 KB Output is correct
40 Correct 6 ms 760 KB Output is correct
41 Correct 6 ms 760 KB Output is correct
42 Correct 6 ms 760 KB Output is correct
43 Correct 6 ms 760 KB Output is correct
44 Correct 6 ms 760 KB Output is correct
45 Correct 6 ms 700 KB Output is correct
46 Correct 6 ms 760 KB Output is correct
47 Correct 6 ms 760 KB Output is correct
48 Execution timed out 2040 ms 66468 KB Time limit exceeded
49 Halted 0 ms 0 KB -