oj.uz

Submission #837947

# Submission time Handle Problem Language Result Execution time Memory
837947 2023-08-25T21:08:56 Z JakobZorz Catfish Farm (IOI22_fish) C++17
47 / 100
 1000 ms 277196 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

# Verdict Execution time Memory Grader output
1 Correct 178 ms 251948 KB Output is correct
2 Correct 183 ms 258336 KB Output is correct
3 Correct 162 ms 248908 KB Output is correct
4 Correct 160 ms 248920 KB Output is correct
5 Correct 277 ms 277196 KB Output is correct
6 Correct 372 ms 273156 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 202312 KB Output is correct
2 Execution timed out 1069 ms 259480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 248852 KB Output is correct
2 Correct 155 ms 248828 KB Output is correct
3 Correct 175 ms 245452 KB Output is correct
4 Correct 177 ms 249720 KB Output is correct
5 Correct 212 ms 251244 KB Output is correct
6 Correct 218 ms 251164 KB Output is correct
7 Correct 204 ms 251244 KB Output is correct
8 Correct 237 ms 251292 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202248 KB Output is correct
2 Correct 96 ms 202184 KB Output is correct
3 Correct 92 ms 202192 KB Output is correct
4 Correct 91 ms 202140 KB Output is correct
5 Correct 89 ms 202256 KB Output is correct
6 Correct 89 ms 202244 KB Output is correct
7 Correct 93 ms 202244 KB Output is correct
8 Correct 90 ms 202252 KB Output is correct
9 Correct 91 ms 202256 KB Output is correct
10 Correct 90 ms 202592 KB Output is correct
11 Correct 90 ms 202312 KB Output is correct
12 Correct 90 ms 202396 KB Output is correct
13 Correct 89 ms 202188 KB Output is correct
14 Correct 92 ms 202332 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202248 KB Output is correct
2 Correct 96 ms 202184 KB Output is correct
3 Correct 92 ms 202192 KB Output is correct
4 Correct 91 ms 202140 KB Output is correct
5 Correct 89 ms 202256 KB Output is correct
6 Correct 89 ms 202244 KB Output is correct
7 Correct 93 ms 202244 KB Output is correct
8 Correct 90 ms 202252 KB Output is correct
9 Correct 91 ms 202256 KB Output is correct
10 Correct 90 ms 202592 KB Output is correct
11 Correct 90 ms 202312 KB Output is correct
12 Correct 90 ms 202396 KB Output is correct
13 Correct 89 ms 202188 KB Output is correct
14 Correct 92 ms 202332 KB Output is correct
15 Correct 90 ms 202316 KB Output is correct
16 Correct 92 ms 202484 KB Output is correct
17 Correct 211 ms 206636 KB Output is correct
18 Correct 237 ms 206920 KB Output is correct
19 Correct 176 ms 206796 KB Output is correct
20 Correct 180 ms 206796 KB Output is correct
21 Correct 192 ms 206928 KB Output is correct
22 Correct 400 ms 211412 KB Output is correct
23 Correct 103 ms 203264 KB Output is correct
24 Correct 134 ms 205196 KB Output is correct
25 Correct 92 ms 202444 KB Output is correct
26 Correct 107 ms 203428 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202248 KB Output is correct
2 Correct 96 ms 202184 KB Output is correct
3 Correct 92 ms 202192 KB Output is correct
4 Correct 91 ms 202140 KB Output is correct
5 Correct 89 ms 202256 KB Output is correct
6 Correct 89 ms 202244 KB Output is correct
7 Correct 93 ms 202244 KB Output is correct
8 Correct 90 ms 202252 KB Output is correct
9 Correct 91 ms 202256 KB Output is correct
10 Correct 90 ms 202592 KB Output is correct
11 Correct 90 ms 202312 KB Output is correct
12 Correct 90 ms 202396 KB Output is correct
13 Correct 89 ms 202188 KB Output is correct
14 Correct 92 ms 202332 KB Output is correct
15 Correct 90 ms 202316 KB Output is correct
16 Correct 92 ms 202484 KB Output is correct
17 Correct 211 ms 206636 KB Output is correct
18 Correct 237 ms 206920 KB Output is correct
19 Correct 176 ms 206796 KB Output is correct
20 Correct 180 ms 206796 KB Output is correct
21 Correct 192 ms 206928 KB Output is correct
22 Correct 400 ms 211412 KB Output is correct
23 Correct 103 ms 203264 KB Output is correct
24 Correct 134 ms 205196 KB Output is correct
25 Correct 92 ms 202444 KB Output is correct
26 Correct 107 ms 203428 KB Output is correct
27 Correct 93 ms 203724 KB Output is correct
28 Execution timed out 1046 ms 224948 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 248852 KB Output is correct
2 Correct 155 ms 248828 KB Output is correct
3 Correct 175 ms 245452 KB Output is correct
4 Correct 177 ms 249720 KB Output is correct
5 Correct 212 ms 251244 KB Output is correct
6 Correct 218 ms 251164 KB Output is correct
7 Correct 204 ms 251244 KB Output is correct
8 Correct 237 ms 251292 KB Output is correct
9 Correct 201 ms 251168 KB Output is correct
10 Correct 168 ms 228884 KB Output is correct
11 Correct 244 ms 255616 KB Output is correct
12 Correct 99 ms 202188 KB Output is correct
13 Correct 91 ms 202232 KB Output is correct
14 Correct 89 ms 202148 KB Output is correct
15 Correct 90 ms 202244 KB Output is correct
16 Correct 91 ms 202188 KB Output is correct
17 Correct 92 ms 202240 KB Output is correct
18 Correct 158 ms 248908 KB Output is correct
19 Correct 159 ms 248908 KB Output is correct
20 Correct 163 ms 249028 KB Output is correct
21 Correct 164 ms 248820 KB Output is correct
22 Incorrect 228 ms 251772 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45551919437846'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 251948 KB Output is correct
2 Correct 183 ms 258336 KB Output is correct
3 Correct 162 ms 248908 KB Output is correct
4 Correct 160 ms 248920 KB Output is correct
5 Correct 277 ms 277196 KB Output is correct
6 Correct 372 ms 273156 KB Output is correct
7 Correct 96 ms 202312 KB Output is correct
8 Execution timed out 1069 ms 259480 KB Time limit exceeded
9 Halted 0 ms 0 KB -