oj.uz

답안 #1055744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1055744 2024-08-13T04:51:48 Z vjudge1 메기 농장 (IOI22_fish) C++17
75 / 100
 1000 ms 98108 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++;
        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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1035 ms 60028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 18264 KB Output is correct
2 Execution timed out 1073 ms 89636 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 68440 KB Output is correct
2 Correct 355 ms 68436 KB Output is correct
3 Correct 399 ms 67920 KB Output is correct
4 Correct 418 ms 71508 KB Output is correct
5 Correct 470 ms 77020 KB Output is correct
6 Correct 459 ms 77136 KB Output is correct
7 Correct 463 ms 77136 KB Output is correct
8 Correct 483 ms 77036 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 18268 KB Output is correct
2 Correct 7 ms 18268 KB Output is correct
3 Correct 6 ms 18352 KB Output is correct
4 Correct 6 ms 18320 KB Output is correct
5 Correct 6 ms 18268 KB Output is correct
6 Correct 6 ms 18268 KB Output is correct
7 Correct 7 ms 18268 KB Output is correct
8 Correct 6 ms 18312 KB Output is correct
9 Correct 8 ms 18524 KB Output is correct
10 Correct 11 ms 18776 KB Output is correct
11 Correct 8 ms 18524 KB Output is correct
12 Correct 9 ms 18736 KB Output is correct
13 Correct 8 ms 18268 KB Output is correct
14 Correct 10 ms 18524 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 18268 KB Output is correct
2 Correct 7 ms 18268 KB Output is correct
3 Correct 6 ms 18352 KB Output is correct
4 Correct 6 ms 18320 KB Output is correct
5 Correct 6 ms 18268 KB Output is correct
6 Correct 6 ms 18268 KB Output is correct
7 Correct 7 ms 18268 KB Output is correct
8 Correct 6 ms 18312 KB Output is correct
9 Correct 8 ms 18524 KB Output is correct
10 Correct 11 ms 18776 KB Output is correct
11 Correct 8 ms 18524 KB Output is correct
12 Correct 9 ms 18736 KB Output is correct
13 Correct 8 ms 18268 KB Output is correct
14 Correct 10 ms 18524 KB Output is correct
15 Correct 10 ms 18524 KB Output is correct
16 Correct 11 ms 18888 KB Output is correct
17 Correct 93 ms 26308 KB Output is correct
18 Correct 107 ms 26964 KB Output is correct
19 Correct 85 ms 26656 KB Output is correct
20 Correct 103 ms 26704 KB Output is correct
21 Correct 88 ms 26704 KB Output is correct
22 Correct 174 ms 35116 KB Output is correct
23 Correct 23 ms 20056 KB Output is correct
24 Correct 63 ms 23712 KB Output is correct
25 Correct 10 ms 18776 KB Output is correct
26 Correct 23 ms 20056 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 18268 KB Output is correct
2 Correct 7 ms 18268 KB Output is correct
3 Correct 6 ms 18352 KB Output is correct
4 Correct 6 ms 18320 KB Output is correct
5 Correct 6 ms 18268 KB Output is correct
6 Correct 6 ms 18268 KB Output is correct
7 Correct 7 ms 18268 KB Output is correct
8 Correct 6 ms 18312 KB Output is correct
9 Correct 8 ms 18524 KB Output is correct
10 Correct 11 ms 18776 KB Output is correct
11 Correct 8 ms 18524 KB Output is correct
12 Correct 9 ms 18736 KB Output is correct
13 Correct 8 ms 18268 KB Output is correct
14 Correct 10 ms 18524 KB Output is correct
15 Correct 10 ms 18524 KB Output is correct
16 Correct 11 ms 18888 KB Output is correct
17 Correct 93 ms 26308 KB Output is correct
18 Correct 107 ms 26964 KB Output is correct
19 Correct 85 ms 26656 KB Output is correct
20 Correct 103 ms 26704 KB Output is correct
21 Correct 88 ms 26704 KB Output is correct
22 Correct 174 ms 35116 KB Output is correct
23 Correct 23 ms 20056 KB Output is correct
24 Correct 63 ms 23712 KB Output is correct
25 Correct 10 ms 18776 KB Output is correct
26 Correct 23 ms 20056 KB Output is correct
27 Correct 24 ms 20312 KB Output is correct
28 Correct 537 ms 58708 KB Output is correct
29 Correct 1000 ms 76888 KB Output is correct
30 Correct 744 ms 71504 KB Output is correct
31 Correct 741 ms 71668 KB Output is correct
32 Correct 657 ms 74832 KB Output is correct
33 Correct 804 ms 71760 KB Output is correct
34 Correct 792 ms 71612 KB Output is correct
35 Correct 224 ms 39760 KB Output is correct
36 Correct 825 ms 74108 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 68440 KB Output is correct
2 Correct 355 ms 68436 KB Output is correct
3 Correct 399 ms 67920 KB Output is correct
4 Correct 418 ms 71508 KB Output is correct
5 Correct 470 ms 77020 KB Output is correct
6 Correct 459 ms 77136 KB Output is correct
7 Correct 463 ms 77136 KB Output is correct
8 Correct 483 ms 77036 KB Output is correct
9 Correct 676 ms 83284 KB Output is correct
10 Correct 306 ms 55124 KB Output is correct
11 Correct 561 ms 91780 KB Output is correct
12 Correct 7 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 18268 KB Output is correct
16 Correct 7 ms 18268 KB Output is correct
17 Correct 7 ms 18268 KB Output is correct
18 Correct 359 ms 68372 KB Output is correct
19 Correct 392 ms 68436 KB Output is correct
20 Correct 361 ms 68488 KB Output is correct
21 Correct 362 ms 68340 KB Output is correct
22 Correct 701 ms 83280 KB Output is correct
23 Correct 609 ms 97872 KB Output is correct
24 Correct 784 ms 98108 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1035 ms 60028 KB Time limit exceeded
2 Halted 0 ms 0 KB -