oj.uz

Submission #1055747

# Submission time Handle Problem Language Result Execution time Memory
1055747 2024-08-13T04:55:05 Z vjudge1 Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 101460 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++;
        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)
            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 1045 ms 60876 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 18268 KB Output is correct
2 Execution timed out 1086 ms 91160 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 68432 KB Output is correct
2 Correct 398 ms 68608 KB Output is correct
3 Correct 421 ms 68944 KB Output is correct
4 Correct 390 ms 72152 KB Output is correct
5 Correct 456 ms 78716 KB Output is correct
6 Correct 464 ms 77968 KB Output is correct
7 Correct 491 ms 78544 KB Output is correct
8 Correct 475 ms 78676 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 18268 KB Output is correct
3 Correct 6 ms 18268 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18268 KB Output is correct
6 Correct 7 ms 18268 KB Output is correct
7 Correct 6 ms 18268 KB Output is correct
8 Correct 7 ms 18216 KB Output is correct
9 Correct 7 ms 18524 KB Output is correct
10 Correct 11 ms 18780 KB Output is correct
11 Correct 8 ms 18524 KB Output is correct
12 Correct 9 ms 18780 KB Output is correct
13 Correct 7 ms 18484 KB Output is correct
14 Correct 9 ms 18520 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 18268 KB Output is correct
3 Correct 6 ms 18268 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18268 KB Output is correct
6 Correct 7 ms 18268 KB Output is correct
7 Correct 6 ms 18268 KB Output is correct
8 Correct 7 ms 18216 KB Output is correct
9 Correct 7 ms 18524 KB Output is correct
10 Correct 11 ms 18780 KB Output is correct
11 Correct 8 ms 18524 KB Output is correct
12 Correct 9 ms 18780 KB Output is correct
13 Correct 7 ms 18484 KB Output is correct
14 Correct 9 ms 18520 KB Output is correct
15 Correct 9 ms 18524 KB Output is correct
16 Correct 11 ms 18792 KB Output is correct
17 Correct 98 ms 26964 KB Output is correct
18 Correct 104 ms 27740 KB Output is correct
19 Correct 88 ms 27440 KB Output is correct
20 Correct 88 ms 27472 KB Output is correct
21 Correct 88 ms 27472 KB Output is correct
22 Correct 176 ms 36688 KB Output is correct
23 Correct 24 ms 20312 KB Output is correct
24 Correct 63 ms 24204 KB Output is correct
25 Correct 10 ms 18776 KB Output is correct
26 Correct 23 ms 20056 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 18268 KB Output is correct
3 Correct 6 ms 18268 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18268 KB Output is correct
6 Correct 7 ms 18268 KB Output is correct
7 Correct 6 ms 18268 KB Output is correct
8 Correct 7 ms 18216 KB Output is correct
9 Correct 7 ms 18524 KB Output is correct
10 Correct 11 ms 18780 KB Output is correct
11 Correct 8 ms 18524 KB Output is correct
12 Correct 9 ms 18780 KB Output is correct
13 Correct 7 ms 18484 KB Output is correct
14 Correct 9 ms 18520 KB Output is correct
15 Correct 9 ms 18524 KB Output is correct
16 Correct 11 ms 18792 KB Output is correct
17 Correct 98 ms 26964 KB Output is correct
18 Correct 104 ms 27740 KB Output is correct
19 Correct 88 ms 27440 KB Output is correct
20 Correct 88 ms 27472 KB Output is correct
21 Correct 88 ms 27472 KB Output is correct
22 Correct 176 ms 36688 KB Output is correct
23 Correct 24 ms 20312 KB Output is correct
24 Correct 63 ms 24204 KB Output is correct
25 Correct 10 ms 18776 KB Output is correct
26 Correct 23 ms 20056 KB Output is correct
27 Correct 28 ms 20192 KB Output is correct
28 Correct 539 ms 61776 KB Output is correct
29 Execution timed out 1034 ms 81488 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 68432 KB Output is correct
2 Correct 398 ms 68608 KB Output is correct
3 Correct 421 ms 68944 KB Output is correct
4 Correct 390 ms 72152 KB Output is correct
5 Correct 456 ms 78716 KB Output is correct
6 Correct 464 ms 77968 KB Output is correct
7 Correct 491 ms 78544 KB Output is correct
8 Correct 475 ms 78676 KB Output is correct
9 Correct 648 ms 84696 KB Output is correct
10 Correct 297 ms 56660 KB Output is correct
11 Correct 604 ms 95056 KB Output is correct
12 Correct 7 ms 18268 KB Output is correct
13 Correct 8 ms 18268 KB Output is correct
14 Correct 6 ms 18268 KB Output is correct
15 Correct 7 ms 18268 KB Output is correct
16 Correct 7 ms 18228 KB Output is correct
17 Correct 6 ms 18444 KB Output is correct
18 Correct 360 ms 68464 KB Output is correct
19 Correct 375 ms 68436 KB Output is correct
20 Correct 356 ms 68432 KB Output is correct
21 Correct 360 ms 68376 KB Output is correct
22 Correct 731 ms 85440 KB Output is correct
23 Correct 666 ms 100948 KB Output is correct
24 Correct 795 ms 101460 KB Output is correct

Subtask #8
0 / 16.0

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