oj.uz

Submission #629321

# Submission time Handle Problem Language Result Execution time Memory
629321 2022-08-14T11:16:53 Z jeff252 Catfish Farm (IOI22_fish) C++17
0 / 100
 170 ms 21724 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=3e5+10;
const int SS=1<<17;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
vector<pair<int,int> > t[N];
struct tr{
    ll seg[(SS<<1)+10];
    void upd(int a,int b,ll x){
        for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
            if(!(a&1)) seg[a+1]=max(seg[a+1],x);
            if(b&1) seg[b-1]=max(seg[b-1],x);
        }
    }
    ll Query(int a){
        ll res=0;
        for(a+=SS;a>0;a>>=1) res=max(res,seg[a]);
        return res;
    }
};
tr dp1,dp2;
ll max_weights(int n,int m,vi x,vi y,vi w){
    for(int i=1;i<=(SS<<1);i++) dp1.seg[i]=0,dp2.seg[i]=0;
    for(int i=0;i<m;i++) t[x[i]+1].push_back({y[i]+1,w[i]});
    for(int i=1;i<=n;i++) sort(t[i].begin(),t[i].end());
    for(int i=1;i<=n;i++){
        int val=dp1.Query(n);
        dp1.upd(0,0,dp2.Query(1));
        int pop=0;
        for(auto [u,c]:t[i]){
            if(pop!=u-1) dp1.upd(pop+1,u-1,dp1.Query(pop));
            dp1.upd(u,u,dp1.Query(u-1)+(ll)c);
            pop=u;
        } 
        if(pop!=n) dp1.upd(pop+1,n,dp1.Query(pop));
        pop=n+1;
        reverse(t[i].begin(),t[i].end());
        for(auto [u,c]:t[i]){
            if(pop!=u+1) dp2.upd(u+1,pop-1,dp2.Query(pop));
            dp2.upd(u,u,dp2.Query(u+1)+(ll)c);
            pop=u;
        } 
        if(pop!=1) dp2.upd(1,pop-1,dp2.Query(pop));
        dp2.upd(1,n+1,val);
    }
    return dp2.Query(1);
}
/*int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int n,m;
    cin>>n>>m;
    vi x,y,w;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        x.push_back(a),y.push_back(b),w.push_back(c);
    } 
    cout<<max_weights(n,m,x,y,w)<<"\n";
}*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 14448 KB Output is correct
2 Correct 70 ms 15280 KB Output is correct
3 Correct 26 ms 11448 KB Output is correct
4 Correct 34 ms 11444 KB Output is correct
5 Incorrect 170 ms 21724 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '45125462312295'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11348 KB Output is correct
2 Incorrect 91 ms 16880 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40482261835302'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11440 KB Output is correct
2 Correct 27 ms 11348 KB Output is correct
3 Incorrect 49 ms 14392 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '2906104169'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11348 KB Output is correct
2 Correct 7 ms 11348 KB Output is correct
3 Correct 6 ms 11344 KB Output is correct
4 Correct 6 ms 11348 KB Output is correct
5 Incorrect 6 ms 11348 KB 1st lines differ - on the 1st token, expected: '8866', found: '16621'
6 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11348 KB Output is correct
2 Correct 7 ms 11348 KB Output is correct
3 Correct 6 ms 11344 KB Output is correct
4 Correct 6 ms 11348 KB Output is correct
5 Incorrect 6 ms 11348 KB 1st lines differ - on the 1st token, expected: '8866', found: '16621'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11348 KB Output is correct
2 Correct 7 ms 11348 KB Output is correct
3 Correct 6 ms 11344 KB Output is correct
4 Correct 6 ms 11348 KB Output is correct
5 Incorrect 6 ms 11348 KB 1st lines differ - on the 1st token, expected: '8866', found: '16621'
6 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11440 KB Output is correct
2 Correct 27 ms 11348 KB Output is correct
3 Incorrect 49 ms 14392 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '2906104169'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 14448 KB Output is correct
2 Correct 70 ms 15280 KB Output is correct
3 Correct 26 ms 11448 KB Output is correct
4 Correct 34 ms 11444 KB Output is correct
5 Incorrect 170 ms 21724 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '45125462312295'
6 Halted 0 ms 0 KB -