oj.uz

Submission #1055771

# Submission time Handle Problem Language Result Execution time Memory
1055771 2024-08-13T05:12:24 Z vjudge1 Catfish Farm (IOI22_fish) C++17
12 / 100
 484 ms 129488 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize(2)
vector<int>fishies[100010];
map<int,ll>fishiess[100010];
unordered_map<int,ll>dp[100010][2];
int N;
inline ll ones(int col,int len){
    return (--fishiess[col].upper_bound(len))->second;
}
struct segtree{
    map<int,ll>mp;
    void reset(){
        mp.clear();
        mp[-1]=-1e18;
    }
    ll query(int pos){
        return (--mp.upper_bound(pos))->second;
    }
    void upd(int p,ll x){
        if(x>(--mp.end())->second)
            mp[p]=x;
    }
};
struct a_data_type{
    segtree Sec,First,Overal,Third;
    inline ll sec(int pos){
        return Sec.query(N-pos);
    }
    inline ll first(int pos){
        return First.query(pos);
    }
    inline ll overal(int pos){
        return Overal.query(N-pos);
    }
    inline ll third(int pos){
        return Third.query(pos);
    }
    void init(int i) {
        Overal.reset(),
        First.reset(),
        Sec.reset(),
        Third.reset();
        for(auto j:fishies[i]){
            j--;
            ll A=dp[i][0][j];
            ll B=dp[i][1][j];
            Overal.upd(N-j,max(A,B));
            First.upd(j,max(A,B)-ones(i+1,j));
            Sec.upd(N-j,A);
            Third.upd(j,B-ones(i,j)-ones(i+1,j));
        }
    }
} likehell[2];
ll max_weights(int N_,int M,vector<int> X,vector<int> Y,vector<int> W) {
    N=N_;
    for(int i=0;i<M;i++)
        fishies[X[i]+1].push_back(Y[i]+1),
        fishiess[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=N;i++){
        fishiess[i][N+1];
        fishiess[i][0];
        auto it=++fishiess[i].begin();
        while(it!=fishiess[i].end())
            it->second+=prev(it)->second,it++;
    }
    for(int i=1;i<=N;i++)
        fishies[i].push_back(1),
        fishies[i].push_back(N+1);
    for(int i=1;i<=N;i++)
        sort(fishies[i].begin(),fishies[i].end());
    fishiess[N+1][0];
    for(auto i:fishies[1])
        dp[1][1][i-1]=ones(2,i-1);
    int b=0;
    likehell[b].init(1);
    likehell[!b].init(0);
    for(int i=2;i<=N;i++){
        for(auto rw:fishies[i]) {
            ll cons=ones(i+1,rw-1)+ones(i-1,rw-1);
            ll F=likehell[!b].first(rw-1);
            ll S=likehell[!b].overal(rw)-ones(i-1,rw-1);
            dp[i][1][rw-1]=cons+max(F,S);
        }
        for(auto rw2:fishies[i]){
            ll cons=ones(i+1,rw2-1)+ones(i-1,rw2-1);
            ll F=likehell[b].third(rw2-1);
            ll S=likehell[b].overal(rw2);
            dp[i][1][rw2-1]=max(dp[i][1][rw2-1],F+cons);
            dp[i][0][rw2-1]=S-ones(i,rw2-1)-ones(i-1,rw2-1)+cons;
        }
        for(auto rw2:fishies[i]) {
            ll K=likehell[b].sec(rw2-1)-ones(i,rw2-1);
            dp[i][0][rw2-1]=max(dp[i][0][rw2-1],ones(i+1,rw2-1)+K);
        }
        b=!b;
        likehell[b].init(i);
    }
    return likehell[b].overal(0);
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 78464 KB Output is correct
2 Correct 162 ms 88220 KB Output is correct
3 Correct 83 ms 68504 KB Output is correct
4 Correct 80 ms 68432 KB Output is correct
5 Correct 484 ms 129488 KB Output is correct
6 Correct 346 ms 121428 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 18268 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 68436 KB Output is correct
2 Correct 105 ms 68476 KB Output is correct
3 Correct 105 ms 68948 KB Output is correct
4 Correct 161 ms 72020 KB Output is correct
5 Correct 165 ms 78676 KB Output is correct
6 Correct 187 ms 77920 KB Output is correct
7 Correct 185 ms 78608 KB Output is correct
8 Correct 153 ms 78544 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 18264 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 18264 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 18264 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 68436 KB Output is correct
2 Correct 105 ms 68476 KB Output is correct
3 Correct 105 ms 68948 KB Output is correct
4 Correct 161 ms 72020 KB Output is correct
5 Correct 165 ms 78676 KB Output is correct
6 Correct 187 ms 77920 KB Output is correct
7 Correct 185 ms 78608 KB Output is correct
8 Correct 153 ms 78544 KB Output is correct
9 Incorrect 180 ms 84724 KB 1st lines differ - on the 1st token, expected: '99999', found: '99998'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 78464 KB Output is correct
2 Correct 162 ms 88220 KB Output is correct
3 Correct 83 ms 68504 KB Output is correct
4 Correct 80 ms 68432 KB Output is correct
5 Correct 484 ms 129488 KB Output is correct
6 Correct 346 ms 121428 KB Output is correct
7 Incorrect 7 ms 18268 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 Halted 0 ms 0 KB -