oj.uz

Submission #373943

# Submission time Handle Problem Language Result Execution time Memory
373943 2021-03-06T08:59:58 Z rrrr10000 Bulldozer (JOI17_bulldozer) C++14
20 / 100
 2000 ms 49992 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<double,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<PP> vpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define pb emplace_back
#define fi first
#define se second
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll inf=1001001001001001001;
ll gcd(ll a,ll b){
    if(b==0)return a;
    return gcd(b,a%b);
}
class segtree{
    vi seg;ll N=1;
public:
    segtree(vi v){
        while(N<v.size())N*=2;
        seg=vi(N*2-1);
        rep(i,v.size())seg[i+N-1]=v[i];
        for(ll i=N-2;i>=0;i--)seg[i]=max(seg[i*2+1],seg[i*2+2]);
    }
    void add(ll i,ll x){
        i+=N-1;
        seg[i]+=x;
        while(i>0){
            i=(i-1)/2;
            seg[i]=max(seg[i*2+1],seg[i*2+2]);
        }
    }
    ll get(ll a,ll b,ll k=0,ll l=0,ll r=-1){
        if(r==-1)r=N;
        if(a<=l&&r<=b)return seg[k];
        if(r<=a||b<=l)return 0;
        ll c1=get(a,b,k*2+1,l,(l+r)/2);
        ll c2=get(a,b,k*2+2,(l+r)/2,r);
        return max(c1,c2);
    }
    void debug(ll n){
        vi res;
        rep(i,n)res.pb(seg[i+N-1]);
        outv(res);
    }
};
int main(){
    ll n;cin>>n;
    vvi tmp(n,vi(3));
    rep(i,n)rep(j,3)cin>>tmp[i][j];
    sort(all(tmp));
    vp v(n);vi val(n);rep(i,n)v[i]=P(tmp[i][0],tmp[i][1]);rep(i,n)val[i]=tmp[i][2];
    vpp srt;
    rep(i,n)rep(j,i){
        ll a=v[i].fi-v[j].fi,b=v[i].se-v[j].se;
        if(a!=0)srt.pb(b/(double)(a),j,i);
        else srt.pb(1001001001001,j,i);
    }
    sort(all(srt));
    ll ans=0;
    for(ll x:val)chmax(ans,x);
    vi num(n),mun(n);
    rep(i,n)num[i]=i;
    rep(i,n)mun[i]=i;
    rep(i,srt.size()){
        ll a=get<1>(srt[i]),b=get<2>(srt[i]);
        ll A=mun[a],B=mun[b];
        assert(B==A+1);
        chmax(ans,val[a]+val[b]);
        ll t=max(0ll,val[a])+max(0ll,val[b]);
        for(int i=A-1;i>=0;i--){
            t+=val[num[i]];chmax(ans,t);
        }
        t=max(0ll,val[a])+max(0ll,val[b]);
        for(int i=B+1;i<n;i++){
            t+=val[num[i]];chmax(ans,t);
        }
        swap(num[A],num[B]);
        swap(mun[a],mun[b]);
    }
    out(ans);
}

Compilation message

bulldozer.cpp: In constructor 'segtree::segtree(vi)':
bulldozer.cpp:34:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while(N<v.size())N*=2;
      |               ~^~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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