oj.uz

답안 #837948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
837948 2023-08-25T21:10:26 Z JakobZorz 메기 농장 (IOI22_fish) C++17
3 / 100
 1000 ms 277236 KB 
#include"fish.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
typedef long long ll;
 
int n;
vector<pair<int,int>>fish[100001];
vector<ll>sum_down[100001];
vector<ll>sum_right[100001];
vector<ll>sum_left[100001];
vector<ll>next_right[100001];
vector<ll>next_left[100001];
int h[100001];
 
vector<ll>dp1[1000001];
vector<bool>dpt1[1000001];
vector<ll>dp2[1000001];
vector<bool>dpt2[1000001];
vector<ll>dp3[1000001];
vector<bool>dpt3[1000001];
ll dp4[1000001];
bool dpt4[1000001];
 
ll get_slope_down(int x,int y);
ll get_slope_up(int x,int y);
ll get_gap(int x,ll min_sum);
ll get_full(int x);
 
ll get1(int y2,int x){
    if(y2<0)
        return LLONG_MIN;
    ll res=get_slope_down(x+1,y2);
    res=max(res,get1(y2-1,x));
    return res;
}
 
ll get_slope_down(int x,int y){
    if(x==n-1){
        return 0;
    }
    
    if(dpt1[x][y])
        return dp1[x][y];
    
    ll res=0;
    for(int y2=0;y2<next_right[x][y];y2++){
        ll res2=get_slope_down(x+1,y2)-sum_down[x][y]+sum_right[x][y];
        
        res=max(res,res2);
    }
    
    ll res2=get_gap(x+1,sum_right[x][y])-sum_down[x][y];
    
    res=max(res,res2);
    
    dpt1[x][y]=true;
    dp1[x][y]=res;
    
    return res;
}

ll get2(int y2,int x){
    if(y2<0)
        return LLONG_MIN;
    ll res=get_slope_up(x+1,y2);
    res=max(res,get2(y2-1,x));
    return res;
}
 
ll get_slope_up(int x,int y){
    if(x==n-1){
        return 0;
    }
    
    if(dpt2[x][y])
        return dp2[x][y];
    
    ll res=0;
    for(int y2=0;y2<h[x+1];y2++){
        if(fish[x][y].first<=fish[x][y2].first){
            ll res2=get_slope_up(x+1,y2)-sum_down[x][y]+sum_left[x][y];
            
            res=max(res,res2);
        }
    }
    
    ll res2=get_full(x+1)+sum_left[x+1].back()-sum_down[x][y]+sum_left[x][y];
    
    res=max(res,res2);
    
    dpt2[x][y]=true;
    dp2[x][y]=res;
    
    return res;
}
 
ll get_gap(int x,ll min_sum){
    if(x==n-1)
        return min_sum;
    
    ll res=0;
    
    res=max(res,get_full(x+1)+sum_left[x+1].back());
    
    for(int y2=0;y2<h[x+1];y2++){
        ll res2=get_slope_up(x+1,y2)+max(sum_left[x+1][y2],min_sum)-sum_left[x+1][y2];
        res=max(res,res2);
    }
    
    return res;
}
 
ll get_full(int x){
    if(x==n-1)
        return 0;
    
    if(dpt4[x])
        return dp4[x];
    
    ll res=0;
    
    res=max(res,get_gap(x+1,sum_right[x].back()));
    
    for(int y2=0;y2<h[x+1];y2++){
        ll res2=get_slope_down(x+1,y2)+sum_right[x].back();
        res=max(res,res2);
    }
    
    dpt4[x]=true;
    dp4[x]=res;
    
    return res;
}
 
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
    n=N+1;
    for(int i=0;i<M;i++)
        fish[X[i]+1].push_back({Y[i],W[i]});
    
    for(int i=0;i<n;i++)
        sort(fish[i].begin(),fish[i].end());
    
    for(int i=0;i<n;i++)
        fish[i].push_back({n,0});
    
    for(int i=0;i<n;i++)
        h[i]=(int)fish[i].size();
    
    for(int i=0;i<n;i++){
        sum_down[i].resize(h[i]);
        for(int j=1;j<h[i];j++){
            sum_down[i][j]=sum_down[i][j-1]+fish[i][j-1].second;
        }
    }
    
    for(int i=0;i<n;i++){
        dp1[i].resize(h[i]);
        dpt1[i].resize(h[i]);
        dp2[i].resize(h[i]);
        dpt2[i].resize(h[i]);
        dp3[i].resize(h[i]);
        dpt3[i].resize(h[i]);
    }
    
    
    sum_right[n-1].resize(h[n-1]);
    for(int i=0;i<n-1;i++){
        sum_right[i].resize(h[i]);
        next_right[i].resize(h[i]);
        int i2=0;
        ll sum=0;
        for(int i1=0;i1<h[i];i1++){
            while(i2<h[i+1]&&fish[i][i1].first>=fish[i+1][i2].first){
                sum+=fish[i+1][i2].second;
                i2++;
            }
            sum_right[i][i1]=sum;
        }
        
        i2=0;
        for(int i1=0;i1<h[i];i1++){
            while(i2<h[i+1]&&fish[i][i1].first>=fish[i+1][i2].first)
                i2++;
            next_right[i][i1]=i2;
        }
    }
    
    sum_left[0].resize(h[0]);
    for(int i=1;i<n;i++){
        sum_left[i].resize(h[i]);
        next_left[i].resize(h[i]);
        int i2=0;
        ll sum=0;
        for(int i1=0;i1<h[i];i1++){
            while(i2<h[i-1]&&fish[i][i1].first>=fish[i-1][i2].first){
                sum+=fish[i-1][i2].second;
                i2++;
            }
            sum_left[i][i1]=sum;
        }
        
        i2=0;
        for(int i1=0;i1<h[i];i1++){
            while(i2<h[i-1]&&fish[i][i1].first>=fish[i-1][i2].first)
                i2++;
            next_left[i][i1]=i2;
        }
    }
    
    return get_gap(0,0);
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 251840 KB Output is correct
2 Correct 188 ms 258320 KB Output is correct
3 Correct 157 ms 248888 KB Output is correct
4 Correct 156 ms 248908 KB Output is correct
5 Correct 274 ms 277236 KB Output is correct
6 Correct 367 ms 273100 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 202188 KB Output is correct
2 Execution timed out 1077 ms 259508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 248832 KB Output is correct
2 Correct 157 ms 248912 KB Output is correct
3 Incorrect 181 ms 245432 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 202188 KB Output is correct
2 Correct 93 ms 202180 KB Output is correct
3 Correct 89 ms 202188 KB Output is correct
4 Correct 92 ms 202188 KB Output is correct
5 Correct 95 ms 202200 KB Output is correct
6 Correct 91 ms 202188 KB Output is correct
7 Correct 93 ms 202220 KB Output is correct
8 Correct 94 ms 202236 KB Output is correct
9 Incorrect 91 ms 202256 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 202188 KB Output is correct
2 Correct 93 ms 202180 KB Output is correct
3 Correct 89 ms 202188 KB Output is correct
4 Correct 92 ms 202188 KB Output is correct
5 Correct 95 ms 202200 KB Output is correct
6 Correct 91 ms 202188 KB Output is correct
7 Correct 93 ms 202220 KB Output is correct
8 Correct 94 ms 202236 KB Output is correct
9 Incorrect 91 ms 202256 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 202188 KB Output is correct
2 Correct 93 ms 202180 KB Output is correct
3 Correct 89 ms 202188 KB Output is correct
4 Correct 92 ms 202188 KB Output is correct
5 Correct 95 ms 202200 KB Output is correct
6 Correct 91 ms 202188 KB Output is correct
7 Correct 93 ms 202220 KB Output is correct
8 Correct 94 ms 202236 KB Output is correct
9 Incorrect 91 ms 202256 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '219109041335'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 248832 KB Output is correct
2 Correct 157 ms 248912 KB Output is correct
3 Incorrect 181 ms 245432 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 251840 KB Output is correct
2 Correct 188 ms 258320 KB Output is correct
3 Correct 157 ms 248888 KB Output is correct
4 Correct 156 ms 248908 KB Output is correct
5 Correct 274 ms 277236 KB Output is correct
6 Correct 367 ms 273100 KB Output is correct
7 Correct 92 ms 202188 KB Output is correct
8 Execution timed out 1077 ms 259508 KB Time limit exceeded
9 Halted 0 ms 0 KB -