oj.uz

Submission #1055753

# Submission time Handle Problem Language Result Execution time Memory
1055753 2024-08-13T04:58:35 Z vjudge1 Catfish Farm (IOI22_fish) C++17
84 / 100
 1000 ms 142236 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{
    ll mp[100100];
    vector<int>v;
    void reset(){
        for(auto i:v)
            mp[i]=0;
        v.clear();
    }
    ll query(int pos){
        ll ans=0;
        pos++;
        while(pos)
            ans=max(ans,mp[pos]),
            pos-=pos&-pos;
        return ans-(1ll<<50);
    }
    void upd(int p,ll x){
        p++;
        assert(p);
        x+=1ll<<50;
        while(p<100100)
            v.push_back(p),
            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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 92488 KB Output is correct
2 Correct 247 ms 104404 KB Output is correct
3 Correct 119 ms 68596 KB Output is correct
4 Correct 101 ms 68688 KB Output is correct
5 Correct 746 ms 142236 KB Output is correct
6 Correct 429 ms 121428 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18736 KB Output is correct
2 Correct 448 ms 120712 KB Output is correct
3 Correct 557 ms 140840 KB Output is correct
4 Correct 212 ms 92548 KB Output is correct
5 Correct 251 ms 104396 KB Output is correct
6 Correct 7 ms 18524 KB Output is correct
7 Correct 7 ms 18524 KB Output is correct
8 Correct 7 ms 18524 KB Output is correct
9 Correct 7 ms 18524 KB Output is correct
10 Correct 99 ms 68824 KB Output is correct
11 Correct 100 ms 68692 KB Output is correct
12 Correct 235 ms 92620 KB Output is correct
13 Correct 267 ms 104576 KB Output is correct
14 Correct 214 ms 93184 KB Output is correct
15 Correct 266 ms 102460 KB Output is correct
16 Correct 208 ms 93076 KB Output is correct
17 Correct 230 ms 102284 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 68696 KB Output is correct
2 Correct 99 ms 68740 KB Output is correct
3 Correct 138 ms 69200 KB Output is correct
4 Correct 145 ms 72400 KB Output is correct
5 Correct 173 ms 78352 KB Output is correct
6 Correct 174 ms 78164 KB Output is correct
7 Correct 193 ms 78420 KB Output is correct
8 Correct 174 ms 78496 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18524 KB Output is correct
2 Correct 8 ms 18524 KB Output is correct
3 Correct 7 ms 18524 KB Output is correct
4 Correct 7 ms 18668 KB Output is correct
5 Correct 7 ms 18528 KB Output is correct
6 Correct 7 ms 18524 KB Output is correct
7 Correct 6 ms 18524 KB Output is correct
8 Correct 6 ms 18748 KB Output is correct
9 Correct 8 ms 18844 KB Output is correct
10 Correct 9 ms 19268 KB Output is correct
11 Correct 7 ms 18760 KB Output is correct
12 Correct 8 ms 19080 KB Output is correct
13 Correct 7 ms 18780 KB Output is correct
14 Correct 9 ms 19036 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18524 KB Output is correct
2 Correct 8 ms 18524 KB Output is correct
3 Correct 7 ms 18524 KB Output is correct
4 Correct 7 ms 18668 KB Output is correct
5 Correct 7 ms 18528 KB Output is correct
6 Correct 7 ms 18524 KB Output is correct
7 Correct 6 ms 18524 KB Output is correct
8 Correct 6 ms 18748 KB Output is correct
9 Correct 8 ms 18844 KB Output is correct
10 Correct 9 ms 19268 KB Output is correct
11 Correct 7 ms 18760 KB Output is correct
12 Correct 8 ms 19080 KB Output is correct
13 Correct 7 ms 18780 KB Output is correct
14 Correct 9 ms 19036 KB Output is correct
15 Correct 7 ms 18836 KB Output is correct
16 Correct 9 ms 19036 KB Output is correct
17 Correct 68 ms 27220 KB Output is correct
18 Correct 73 ms 27888 KB Output is correct
19 Correct 74 ms 27440 KB Output is correct
20 Correct 77 ms 27472 KB Output is correct
21 Correct 66 ms 27476 KB Output is correct
22 Correct 141 ms 36732 KB Output is correct
23 Correct 16 ms 20572 KB Output is correct
24 Correct 43 ms 24356 KB Output is correct
25 Correct 8 ms 19032 KB Output is correct
26 Correct 16 ms 20368 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18524 KB Output is correct
2 Correct 8 ms 18524 KB Output is correct
3 Correct 7 ms 18524 KB Output is correct
4 Correct 7 ms 18668 KB Output is correct
5 Correct 7 ms 18528 KB Output is correct
6 Correct 7 ms 18524 KB Output is correct
7 Correct 6 ms 18524 KB Output is correct
8 Correct 6 ms 18748 KB Output is correct
9 Correct 8 ms 18844 KB Output is correct
10 Correct 9 ms 19268 KB Output is correct
11 Correct 7 ms 18760 KB Output is correct
12 Correct 8 ms 19080 KB Output is correct
13 Correct 7 ms 18780 KB Output is correct
14 Correct 9 ms 19036 KB Output is correct
15 Correct 7 ms 18836 KB Output is correct
16 Correct 9 ms 19036 KB Output is correct
17 Correct 68 ms 27220 KB Output is correct
18 Correct 73 ms 27888 KB Output is correct
19 Correct 74 ms 27440 KB Output is correct
20 Correct 77 ms 27472 KB Output is correct
21 Correct 66 ms 27476 KB Output is correct
22 Correct 141 ms 36732 KB Output is correct
23 Correct 16 ms 20572 KB Output is correct
24 Correct 43 ms 24356 KB Output is correct
25 Correct 8 ms 19032 KB Output is correct
26 Correct 16 ms 20368 KB Output is correct
27 Correct 11 ms 20828 KB Output is correct
28 Correct 376 ms 61104 KB Output is correct
29 Correct 666 ms 80440 KB Output is correct
30 Correct 419 ms 75000 KB Output is correct
31 Correct 442 ms 75148 KB Output is correct
32 Correct 554 ms 78048 KB Output is correct
33 Correct 439 ms 74888 KB Output is correct
34 Correct 436 ms 75220 KB Output is correct
35 Correct 148 ms 41536 KB Output is correct
36 Correct 487 ms 77644 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 68696 KB Output is correct
2 Correct 99 ms 68740 KB Output is correct
3 Correct 138 ms 69200 KB Output is correct
4 Correct 145 ms 72400 KB Output is correct
5 Correct 173 ms 78352 KB Output is correct
6 Correct 174 ms 78164 KB Output is correct
7 Correct 193 ms 78420 KB Output is correct
8 Correct 174 ms 78496 KB Output is correct
9 Correct 187 ms 90636 KB Output is correct
10 Correct 131 ms 56656 KB Output is correct
11 Correct 246 ms 94548 KB Output is correct
12 Correct 8 ms 18524 KB Output is correct
13 Correct 7 ms 18704 KB Output is correct
14 Correct 7 ms 18520 KB Output is correct
15 Correct 8 ms 18520 KB Output is correct
16 Correct 6 ms 18524 KB Output is correct
17 Correct 6 ms 18524 KB Output is correct
18 Correct 122 ms 68692 KB Output is correct
19 Correct 136 ms 68692 KB Output is correct
20 Correct 120 ms 68688 KB Output is correct
21 Correct 96 ms 68700 KB Output is correct
22 Correct 207 ms 90708 KB Output is correct
23 Correct 270 ms 100096 KB Output is correct
24 Correct 278 ms 100936 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 92488 KB Output is correct
2 Correct 247 ms 104404 KB Output is correct
3 Correct 119 ms 68596 KB Output is correct
4 Correct 101 ms 68688 KB Output is correct
5 Correct 746 ms 142236 KB Output is correct
6 Correct 429 ms 121428 KB Output is correct
7 Correct 7 ms 18736 KB Output is correct
8 Correct 448 ms 120712 KB Output is correct
9 Correct 557 ms 140840 KB Output is correct
10 Correct 212 ms 92548 KB Output is correct
11 Correct 251 ms 104396 KB Output is correct
12 Correct 7 ms 18524 KB Output is correct
13 Correct 7 ms 18524 KB Output is correct
14 Correct 7 ms 18524 KB Output is correct
15 Correct 7 ms 18524 KB Output is correct
16 Correct 99 ms 68824 KB Output is correct
17 Correct 100 ms 68692 KB Output is correct
18 Correct 235 ms 92620 KB Output is correct
19 Correct 267 ms 104576 KB Output is correct
20 Correct 214 ms 93184 KB Output is correct
21 Correct 266 ms 102460 KB Output is correct
22 Correct 208 ms 93076 KB Output is correct
23 Correct 230 ms 102284 KB Output is correct
24 Correct 98 ms 68696 KB Output is correct
25 Correct 99 ms 68740 KB Output is correct
26 Correct 138 ms 69200 KB Output is correct
27 Correct 145 ms 72400 KB Output is correct
28 Correct 173 ms 78352 KB Output is correct
29 Correct 174 ms 78164 KB Output is correct
30 Correct 193 ms 78420 KB Output is correct
31 Correct 174 ms 78496 KB Output is correct
32 Correct 7 ms 18524 KB Output is correct
33 Correct 8 ms 18524 KB Output is correct
34 Correct 7 ms 18524 KB Output is correct
35 Correct 7 ms 18668 KB Output is correct
36 Correct 7 ms 18528 KB Output is correct
37 Correct 7 ms 18524 KB Output is correct
38 Correct 6 ms 18524 KB Output is correct
39 Correct 6 ms 18748 KB Output is correct
40 Correct 8 ms 18844 KB Output is correct
41 Correct 9 ms 19268 KB Output is correct
42 Correct 7 ms 18760 KB Output is correct
43 Correct 8 ms 19080 KB Output is correct
44 Correct 7 ms 18780 KB Output is correct
45 Correct 9 ms 19036 KB Output is correct
46 Correct 7 ms 18836 KB Output is correct
47 Correct 9 ms 19036 KB Output is correct
48 Correct 68 ms 27220 KB Output is correct
49 Correct 73 ms 27888 KB Output is correct
50 Correct 74 ms 27440 KB Output is correct
51 Correct 77 ms 27472 KB Output is correct
52 Correct 66 ms 27476 KB Output is correct
53 Correct 141 ms 36732 KB Output is correct
54 Correct 16 ms 20572 KB Output is correct
55 Correct 43 ms 24356 KB Output is correct
56 Correct 8 ms 19032 KB Output is correct
57 Correct 16 ms 20368 KB Output is correct
58 Correct 11 ms 20828 KB Output is correct
59 Correct 376 ms 61104 KB Output is correct
60 Correct 666 ms 80440 KB Output is correct
61 Correct 419 ms 75000 KB Output is correct
62 Correct 442 ms 75148 KB Output is correct
63 Correct 554 ms 78048 KB Output is correct
64 Correct 439 ms 74888 KB Output is correct
65 Correct 436 ms 75220 KB Output is correct
66 Correct 148 ms 41536 KB Output is correct
67 Correct 487 ms 77644 KB Output is correct
68 Correct 187 ms 90636 KB Output is correct
69 Correct 131 ms 56656 KB Output is correct
70 Correct 246 ms 94548 KB Output is correct
71 Correct 8 ms 18524 KB Output is correct
72 Correct 7 ms 18704 KB Output is correct
73 Correct 7 ms 18520 KB Output is correct
74 Correct 8 ms 18520 KB Output is correct
75 Correct 6 ms 18524 KB Output is correct
76 Correct 6 ms 18524 KB Output is correct
77 Correct 122 ms 68692 KB Output is correct
78 Correct 136 ms 68692 KB Output is correct
79 Correct 120 ms 68688 KB Output is correct
80 Correct 96 ms 68700 KB Output is correct
81 Correct 207 ms 90708 KB Output is correct
82 Correct 270 ms 100096 KB Output is correct
83 Correct 278 ms 100936 KB Output is correct
84 Execution timed out 1004 ms 128840 KB Time limit exceeded
85 Halted 0 ms 0 KB -