oj.uz

Submission #1055746

# Submission time Handle Problem Language Result Execution time Memory
1055746 2024-08-13T04:54:23 Z vjudge1 Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 102188 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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{
    unordered_map<int,ll>mp;
    void reset(){mp.clear();}
    ll query(int pos){
        ll ans=0;
        pos+=2;
        while(pos)
            ans=max(ans,mp[pos]),
            pos-=pos&-pos;
        return ans-(1ll<<50);
    }
    void upd(int p,ll x){
        p+=2;
        x+=1ll<<50;
        while(p<100100)
            mp[p]=max(mp[p],x),
            p+=p&-p;
    }
};
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);
    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);
    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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 61568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18264 KB Output is correct
2 Execution timed out 1092 ms 92588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 68436 KB Output is correct
2 Correct 335 ms 68436 KB Output is correct
3 Correct 397 ms 68944 KB Output is correct
4 Correct 413 ms 72276 KB Output is correct
5 Correct 438 ms 78672 KB Output is correct
6 Correct 471 ms 77908 KB Output is correct
7 Correct 457 ms 78672 KB Output is correct
8 Correct 445 ms 78672 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18264 KB Output is correct
2 Correct 6 ms 18296 KB Output is correct
3 Correct 7 ms 18268 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18400 KB Output is correct
6 Correct 7 ms 18268 KB Output is correct
7 Correct 7 ms 18264 KB Output is correct
8 Correct 7 ms 18268 KB Output is correct
9 Correct 8 ms 18524 KB Output is correct
10 Correct 10 ms 18780 KB Output is correct
11 Correct 8 ms 18508 KB Output is correct
12 Correct 9 ms 18796 KB Output is correct
13 Correct 7 ms 18268 KB Output is correct
14 Correct 9 ms 18524 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18264 KB Output is correct
2 Correct 6 ms 18296 KB Output is correct
3 Correct 7 ms 18268 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18400 KB Output is correct
6 Correct 7 ms 18268 KB Output is correct
7 Correct 7 ms 18264 KB Output is correct
8 Correct 7 ms 18268 KB Output is correct
9 Correct 8 ms 18524 KB Output is correct
10 Correct 10 ms 18780 KB Output is correct
11 Correct 8 ms 18508 KB Output is correct
12 Correct 9 ms 18796 KB Output is correct
13 Correct 7 ms 18268 KB Output is correct
14 Correct 9 ms 18524 KB Output is correct
15 Correct 10 ms 18524 KB Output is correct
16 Correct 11 ms 18776 KB Output is correct
17 Correct 90 ms 27096 KB Output is correct
18 Correct 96 ms 27788 KB Output is correct
19 Correct 85 ms 27332 KB Output is correct
20 Correct 86 ms 27396 KB Output is correct
21 Correct 85 ms 27488 KB Output is correct
22 Correct 174 ms 36692 KB Output is correct
23 Correct 23 ms 20316 KB Output is correct
24 Correct 62 ms 24132 KB Output is correct
25 Correct 10 ms 18776 KB Output is correct
26 Correct 23 ms 20060 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18264 KB Output is correct
2 Correct 6 ms 18296 KB Output is correct
3 Correct 7 ms 18268 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18400 KB Output is correct
6 Correct 7 ms 18268 KB Output is correct
7 Correct 7 ms 18264 KB Output is correct
8 Correct 7 ms 18268 KB Output is correct
9 Correct 8 ms 18524 KB Output is correct
10 Correct 10 ms 18780 KB Output is correct
11 Correct 8 ms 18508 KB Output is correct
12 Correct 9 ms 18796 KB Output is correct
13 Correct 7 ms 18268 KB Output is correct
14 Correct 9 ms 18524 KB Output is correct
15 Correct 10 ms 18524 KB Output is correct
16 Correct 11 ms 18776 KB Output is correct
17 Correct 90 ms 27096 KB Output is correct
18 Correct 96 ms 27788 KB Output is correct
19 Correct 85 ms 27332 KB Output is correct
20 Correct 86 ms 27396 KB Output is correct
21 Correct 85 ms 27488 KB Output is correct
22 Correct 174 ms 36692 KB Output is correct
23 Correct 23 ms 20316 KB Output is correct
24 Correct 62 ms 24132 KB Output is correct
25 Correct 10 ms 18776 KB Output is correct
26 Correct 23 ms 20060 KB Output is correct
27 Correct 23 ms 20312 KB Output is correct
28 Correct 549 ms 62548 KB Output is correct
29 Execution timed out 1000 ms 82476 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 68436 KB Output is correct
2 Correct 335 ms 68436 KB Output is correct
3 Correct 397 ms 68944 KB Output is correct
4 Correct 413 ms 72276 KB Output is correct
5 Correct 438 ms 78672 KB Output is correct
6 Correct 471 ms 77908 KB Output is correct
7 Correct 457 ms 78672 KB Output is correct
8 Correct 445 ms 78672 KB Output is correct
9 Correct 634 ms 84564 KB Output is correct
10 Correct 287 ms 56916 KB Output is correct
11 Correct 582 ms 95272 KB Output is correct
12 Correct 8 ms 18268 KB Output is correct
13 Correct 7 ms 18268 KB Output is correct
14 Correct 7 ms 18268 KB Output is correct
15 Correct 6 ms 18252 KB Output is correct
16 Correct 7 ms 18456 KB Output is correct
17 Correct 9 ms 18316 KB Output is correct
18 Correct 339 ms 68436 KB Output is correct
19 Correct 365 ms 68436 KB Output is correct
20 Correct 363 ms 68284 KB Output is correct
21 Correct 348 ms 68428 KB Output is correct
22 Correct 679 ms 85328 KB Output is correct
23 Correct 607 ms 101296 KB Output is correct
24 Correct 805 ms 102188 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 61568 KB Time limit exceeded
2 Halted 0 ms 0 KB -