oj.uz

답안 #837946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
837946 2023-08-25T21:07:24 Z JakobZorz 메기 농장 (IOI22_fish) C++17
26 / 100
 1000 ms 278688 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=get1(next_right[x][y]-1,x)-sum_down[x][y]+sum_right[x][y];
    
    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 215 ms 252008 KB Output is correct
2 Correct 193 ms 258300 KB Output is correct
3 Correct 160 ms 248908 KB Output is correct
4 Correct 163 ms 248860 KB Output is correct
5 Correct 289 ms 278688 KB Output is correct
6 Correct 373 ms 273104 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 248908 KB Output is correct
2 Correct 166 ms 248940 KB Output is correct
3 Correct 183 ms 245452 KB Output is correct
4 Correct 179 ms 249932 KB Output is correct
5 Correct 213 ms 251724 KB Output is correct
6 Correct 207 ms 251724 KB Output is correct
7 Correct 209 ms 251732 KB Output is correct
8 Correct 210 ms 251672 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 202184 KB Output is correct
2 Correct 96 ms 202188 KB Output is correct
3 Correct 91 ms 202260 KB Output is correct
4 Correct 92 ms 202216 KB Output is correct
5 Correct 97 ms 202208 KB Output is correct
6 Correct 95 ms 202148 KB Output is correct
7 Correct 93 ms 202156 KB Output is correct
8 Correct 96 ms 202280 KB Output is correct
9 Correct 90 ms 202316 KB Output is correct
10 Correct 93 ms 202512 KB Output is correct
11 Correct 93 ms 202332 KB Output is correct
12 Correct 94 ms 202476 KB Output is correct
13 Correct 92 ms 202224 KB Output is correct
14 Correct 93 ms 202376 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 202184 KB Output is correct
2 Correct 96 ms 202188 KB Output is correct
3 Correct 91 ms 202260 KB Output is correct
4 Correct 92 ms 202216 KB Output is correct
5 Correct 97 ms 202208 KB Output is correct
6 Correct 95 ms 202148 KB Output is correct
7 Correct 93 ms 202156 KB Output is correct
8 Correct 96 ms 202280 KB Output is correct
9 Correct 90 ms 202316 KB Output is correct
10 Correct 93 ms 202512 KB Output is correct
11 Correct 93 ms 202332 KB Output is correct
12 Correct 94 ms 202476 KB Output is correct
13 Correct 92 ms 202224 KB Output is correct
14 Correct 93 ms 202376 KB Output is correct
15 Correct 92 ms 202412 KB Output is correct
16 Correct 94 ms 202444 KB Output is correct
17 Correct 216 ms 207380 KB Output is correct
18 Correct 229 ms 207564 KB Output is correct
19 Correct 183 ms 207588 KB Output is correct
20 Correct 178 ms 207524 KB Output is correct
21 Correct 182 ms 207376 KB Output is correct
22 Correct 399 ms 212104 KB Output is correct
23 Correct 101 ms 203324 KB Output is correct
24 Correct 139 ms 205628 KB Output is correct
25 Incorrect 93 ms 202480 KB 1st lines differ - on the 1st token, expected: '443843838929', found: '443838091417'
26 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 202184 KB Output is correct
2 Correct 96 ms 202188 KB Output is correct
3 Correct 91 ms 202260 KB Output is correct
4 Correct 92 ms 202216 KB Output is correct
5 Correct 97 ms 202208 KB Output is correct
6 Correct 95 ms 202148 KB Output is correct
7 Correct 93 ms 202156 KB Output is correct
8 Correct 96 ms 202280 KB Output is correct
9 Correct 90 ms 202316 KB Output is correct
10 Correct 93 ms 202512 KB Output is correct
11 Correct 93 ms 202332 KB Output is correct
12 Correct 94 ms 202476 KB Output is correct
13 Correct 92 ms 202224 KB Output is correct
14 Correct 93 ms 202376 KB Output is correct
15 Correct 92 ms 202412 KB Output is correct
16 Correct 94 ms 202444 KB Output is correct
17 Correct 216 ms 207380 KB Output is correct
18 Correct 229 ms 207564 KB Output is correct
19 Correct 183 ms 207588 KB Output is correct
20 Correct 178 ms 207524 KB Output is correct
21 Correct 182 ms 207376 KB Output is correct
22 Correct 399 ms 212104 KB Output is correct
23 Correct 101 ms 203324 KB Output is correct
24 Correct 139 ms 205628 KB Output is correct
25 Incorrect 93 ms 202480 KB 1st lines differ - on the 1st token, expected: '443843838929', found: '443838091417'
26 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 248908 KB Output is correct
2 Correct 166 ms 248940 KB Output is correct
3 Correct 183 ms 245452 KB Output is correct
4 Correct 179 ms 249932 KB Output is correct
5 Correct 213 ms 251724 KB Output is correct
6 Correct 207 ms 251724 KB Output is correct
7 Correct 209 ms 251732 KB Output is correct
8 Correct 210 ms 251672 KB Output is correct
9 Correct 210 ms 251208 KB Output is correct
10 Correct 184 ms 228892 KB Output is correct
11 Correct 246 ms 255692 KB Output is correct
12 Correct 98 ms 202160 KB Output is correct
13 Correct 95 ms 202188 KB Output is correct
14 Correct 91 ms 202248 KB Output is correct
15 Correct 94 ms 202224 KB Output is correct
16 Correct 94 ms 202188 KB Output is correct
17 Correct 93 ms 202208 KB Output is correct
18 Correct 160 ms 248840 KB Output is correct
19 Correct 167 ms 248908 KB Output is correct
20 Correct 167 ms 248912 KB Output is correct
21 Correct 157 ms 248876 KB Output is correct
22 Incorrect 213 ms 251732 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45551264637704'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 252008 KB Output is correct
2 Correct 193 ms 258300 KB Output is correct
3 Correct 160 ms 248908 KB Output is correct
4 Correct 163 ms 248860 KB Output is correct
5 Correct 289 ms 278688 KB Output is correct
6 Correct 373 ms 273104 KB Output is correct
7 Correct 95 ms 202188 KB Output is correct
8 Execution timed out 1117 ms 260320 KB Time limit exceeded
9 Halted 0 ms 0 KB -