oj.uz

답안 #1023094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1023094 2024-07-14T09:36:00 Z vjudge1 메기 농장 (IOI22_fish) C++17
18 / 100
 195 ms 108600 KB 
#include "fish.h"
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define lb lower_bound
#define ub upper_bound
#define mem(a,i) memset(a,i,sizeof(a))

const int MAX=2e5+10;

int n;
vector<pair<ll,ll>> y[MAX];
vector<ll> p[MAX];
vector<vector<ll>> dp[MAX];
vector<ll> can[MAX];

ll getSum(int x,ll l,ll r){
    if(l>r)return 0;
    int L=lb(all(y[x]),make_pair(l,0ll))-y[x].begin();
    int R=ub(all(y[x]),make_pair(r+1,0ll))-y[x].begin()-1;
    if(L<=R){
        if(L==0)return p[x][R];
        return p[x][R]-p[x][L-1];
    }
    return 0;
}

vector<vector<ll>> sumF[MAX];
vector<vector<ll>> sumB[MAX];
vector<pair<int,int>> vec[MAX];
vector<vector<ll>> w;
ll P[310][310][2];

struct t300{

    ll dp[310][310][2];

    ll getP(int i,int l,int r){
        if(l>r||i==0)return 0;
        return p[i][r]-p[i][l-1];
    }

    ll solve300(){
        for(int i=1;i<=n;i++){
            p[i].resize(n+10);
            p[i][0]=0;
            for(int j=1;j<=n;j++){
                p[i][j]=p[i][j-1]+w[i][j];
            }
        }
        mem(dp,0);
        mem(P,0);
        for(int i=2;i<=n;i++){
            for(int j=0;j<=n;j++){
                {
                    dp[i][j][0]=P[i-1][j][0]-p[i][j];
                }
                {
                    for(int f=0;f<=j;f++){
                        dp[i][j][1]=max(dp[i][j][1],dp[i-1][f][1]+getP(i-1,f+1,j));
                    }
                    dp[i][j][1]=max(dp[i][j][1],dp[i-1][0][0]);
                }
            }
            for(int j=n;j>=0;j--){
                // push[i][j][0]=p[i+1][j];
                p[i+1][j];
                // P[i]
                // push[i][j][0];
            }
        }
        ll ans=0;
        for(int j=0;j<=n;j++)ans=max(ans,max(dp[n][j][0],dp[n][j][1]));
        return ans;
    }
};


long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) {
    // assert(N<=300);
    n=N;
    int MX=0;
    bool sub=1;
    for(int i=0;i<M;i++){
        X[i]++;
        Y[i]++;
        y[X[i]].pb({Y[i],i});
        vec[Y[i]].pb({X[i],W[i]});
        sub&=(X[i]%2==1);
        MX=max(MX,X[i]);
    }
    if(sub){
        ll ans=0;
        for(int i=0;i<M;i++)ans+=W[i];
        return ans;
    }
    if(MX<=2){
        if(N==2){
            ll f=0,f1=0;
            for(int i=0;i<M;i++){
                if(X[i]%2)f+=W[i];
                else f1+=W[i];
            }
            return max(f,f1);
        }
        ll sum=0;
        for(int i=0;i<M;i++){
            if(X[i]%2==0)sum+=W[i];
        }
        ll ans=sum;
        for(int i=1;i<=N;i++){
            for(auto [x,w]:vec[i]){
                if(x%2==1)sum+=w;
                else sum-=w;
            }
            ans=max(ans,sum);
        }
        return ans;
    }
    for(int i=1;i<=N;i++){
        if(y[i].empty())continue;
        sort(all(y[i]));
        p[i].pb(W[y[i][0].S]);
        for(int j=1;j<sz(y[i]);j++){
            p[i].pb(p[i].back()+W[y[i][j].S]);
        }
    }
    if(N<=300){
        w.resize(N+10);
        for(int i=1;i<=n;i++){
            w[i].resize(n+10);
            for(int j=1;j<=n;j++){
                w[i][j]=0;
            }
            for(auto [pos,num]:y[i])w[i][pos]=W[num];
        }
        t300 FFF;
        return FFF.solve300();
    }
    can[0].pb(0);
    can[N+1].pb(0);
    for(int i=1;i<=N;i++){
        can[i].pb(0);
        if(i>0){
            for(auto [x,b]:y[i-1])can[i].pb(x);
        }
        if(i+1<=N){
            for(auto [x,b]:y[i+1])can[i].pb(x);
        }
        sort(all(can[i]));
        can[i].erase(unique(all(can[i])),can[i].end());
    }
    for(int i=1;i<=N+1;i++){
        dp[i].resize(sz(can[i]));
        for(int j=0;j<sz(dp[i]);j++){
            dp[i][j].resize(sz(can[i-1]));
            for(int k=0;k<sz(can[i-1]);k++){
                dp[i][j][k]=0;
            }
        }
    }
    for(int i=0;i<N;i++){
        sumF[i].resize(sz(can[i]));
        for(int j=0;j<sz(can[i]);j++){
            sumF[i][j].resize(sz(can[i+1]));
            for(int k=0;k<sz(can[i+1]);k++){
                sumF[i][j][k]=getSum(i+1,can[i+1][k]+1,can[i][j]);
            }
        }
    }
    for(int i=1;i<=N+1;i++){
        sumB[i].resize(sz(can[i]));
        for(int j=0;j<sz(can[i]);j++){
            sumB[i][j].resize(sz(can[i-1]));
            for(int k=0;k<sz(can[i-1]);k++){
                sumB[i][j][k]=getSum(i-1,can[i-1][k]+1,can[i][j]);
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<sz(can[i]);j++){
            for(int k=0;k<sz(can[i-1]);k++){
                for(int f=0;f<sz(can[i+1]);f++){
                    ll nxt=dp[i][j][k];
                    {
                        nxt+=max(sumF[i-1][k][j],sumB[i+1][f][j]);
                    }
                    dp[i+1][f][j]=max(dp[i+1][f][j],nxt);
                }
            }
        }
    }
    ll ans=0;
    for(int j=0;j<sz(can[N]);j++)ans=max(ans,dp[N+1][0][j]);
    return ans;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 40600 KB Output is correct
2 Correct 43 ms 41828 KB Output is correct
3 Correct 14 ms 34820 KB Output is correct
4 Correct 15 ms 34616 KB Output is correct
5 Correct 102 ms 51520 KB Output is correct
6 Correct 110 ms 53840 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 34652 KB Output is correct
2 Correct 58 ms 44340 KB Output is correct
3 Correct 73 ms 45580 KB Output is correct
4 Correct 38 ms 40588 KB Output is correct
5 Correct 44 ms 41664 KB Output is correct
6 Correct 14 ms 34652 KB Output is correct
7 Correct 14 ms 34652 KB Output is correct
8 Correct 14 ms 34652 KB Output is correct
9 Correct 14 ms 34652 KB Output is correct
10 Correct 14 ms 34652 KB Output is correct
11 Correct 14 ms 34652 KB Output is correct
12 Correct 34 ms 40824 KB Output is correct
13 Correct 43 ms 41664 KB Output is correct
14 Correct 41 ms 40508 KB Output is correct
15 Correct 37 ms 39744 KB Output is correct
16 Correct 35 ms 40516 KB Output is correct
17 Correct 42 ms 41028 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 34676 KB Output is correct
2 Correct 46 ms 56584 KB Output is correct
3 Correct 80 ms 71252 KB Output is correct
4 Correct 72 ms 68040 KB Output is correct
5 Correct 114 ms 86468 KB Output is correct
6 Correct 104 ms 86240 KB Output is correct
7 Correct 113 ms 86332 KB Output is correct
8 Correct 115 ms 86468 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 36316 KB Output is correct
2 Correct 16 ms 36184 KB Output is correct
3 Correct 14 ms 34700 KB Output is correct
4 Correct 14 ms 34648 KB Output is correct
5 Correct 14 ms 34588 KB Output is correct
6 Correct 14 ms 34652 KB Output is correct
7 Correct 15 ms 34652 KB Output is correct
8 Incorrect 14 ms 36156 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 36316 KB Output is correct
2 Correct 16 ms 36184 KB Output is correct
3 Correct 14 ms 34700 KB Output is correct
4 Correct 14 ms 34648 KB Output is correct
5 Correct 14 ms 34588 KB Output is correct
6 Correct 14 ms 34652 KB Output is correct
7 Correct 15 ms 34652 KB Output is correct
8 Incorrect 14 ms 36156 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 36316 KB Output is correct
2 Correct 16 ms 36184 KB Output is correct
3 Correct 14 ms 34700 KB Output is correct
4 Correct 14 ms 34648 KB Output is correct
5 Correct 14 ms 34588 KB Output is correct
6 Correct 14 ms 34652 KB Output is correct
7 Correct 15 ms 34652 KB Output is correct
8 Incorrect 14 ms 36156 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 34676 KB Output is correct
2 Correct 46 ms 56584 KB Output is correct
3 Correct 80 ms 71252 KB Output is correct
4 Correct 72 ms 68040 KB Output is correct
5 Correct 114 ms 86468 KB Output is correct
6 Correct 104 ms 86240 KB Output is correct
7 Correct 113 ms 86332 KB Output is correct
8 Correct 115 ms 86468 KB Output is correct
9 Correct 195 ms 102740 KB Output is correct
10 Correct 135 ms 71492 KB Output is correct
11 Correct 173 ms 108600 KB Output is correct
12 Correct 14 ms 34652 KB Output is correct
13 Correct 14 ms 34744 KB Output is correct
14 Correct 13 ms 34652 KB Output is correct
15 Correct 15 ms 34828 KB Output is correct
16 Correct 13 ms 34692 KB Output is correct
17 Incorrect 14 ms 36276 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
18 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 40600 KB Output is correct
2 Correct 43 ms 41828 KB Output is correct
3 Correct 14 ms 34820 KB Output is correct
4 Correct 15 ms 34616 KB Output is correct
5 Correct 102 ms 51520 KB Output is correct
6 Correct 110 ms 53840 KB Output is correct
7 Correct 14 ms 34652 KB Output is correct
8 Correct 58 ms 44340 KB Output is correct
9 Correct 73 ms 45580 KB Output is correct
10 Correct 38 ms 40588 KB Output is correct
11 Correct 44 ms 41664 KB Output is correct
12 Correct 14 ms 34652 KB Output is correct
13 Correct 14 ms 34652 KB Output is correct
14 Correct 14 ms 34652 KB Output is correct
15 Correct 14 ms 34652 KB Output is correct
16 Correct 14 ms 34652 KB Output is correct
17 Correct 14 ms 34652 KB Output is correct
18 Correct 34 ms 40824 KB Output is correct
19 Correct 43 ms 41664 KB Output is correct
20 Correct 41 ms 40508 KB Output is correct
21 Correct 37 ms 39744 KB Output is correct
22 Correct 35 ms 40516 KB Output is correct
23 Correct 42 ms 41028 KB Output is correct
24 Correct 14 ms 34676 KB Output is correct
25 Correct 46 ms 56584 KB Output is correct
26 Correct 80 ms 71252 KB Output is correct
27 Correct 72 ms 68040 KB Output is correct
28 Correct 114 ms 86468 KB Output is correct
29 Correct 104 ms 86240 KB Output is correct
30 Correct 113 ms 86332 KB Output is correct
31 Correct 115 ms 86468 KB Output is correct
32 Correct 17 ms 36316 KB Output is correct
33 Correct 16 ms 36184 KB Output is correct
34 Correct 14 ms 34700 KB Output is correct
35 Correct 14 ms 34648 KB Output is correct
36 Correct 14 ms 34588 KB Output is correct
37 Correct 14 ms 34652 KB Output is correct
38 Correct 15 ms 34652 KB Output is correct
39 Incorrect 14 ms 36156 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
40 Halted 0 ms 0 KB -