oj.uz

Submission #837935

# Submission time Handle Problem Language Result Execution time Memory
837935 2023-08-25T20:45:44 Z JakobZorz Catfish Farm (IOI22_fish) C++17
26 / 100
 1000 ms 279836 KB 
#include"fish.h"
#include<vector>
#include<iostream>
#include<algorithm>
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 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 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;
            next_right[i][i1]=i2-1;
        }
    }
    
    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;
            next_left[i][i1]=i2-1;
        }
    }
    
    return get_gap(0,0);
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 252008 KB Output is correct
2 Correct 188 ms 260076 KB Output is correct
3 Correct 154 ms 248840 KB Output is correct
4 Correct 160 ms 248964 KB Output is correct
5 Correct 286 ms 279828 KB Output is correct
6 Correct 366 ms 279836 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 202256 KB Output is correct
2 Execution timed out 1087 ms 259664 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 248920 KB Output is correct
2 Correct 159 ms 248880 KB Output is correct
3 Correct 175 ms 246400 KB Output is correct
4 Correct 180 ms 249908 KB Output is correct
5 Correct 208 ms 251304 KB Output is correct
6 Correct 205 ms 251364 KB Output is correct
7 Correct 213 ms 251592 KB Output is correct
8 Correct 204 ms 251376 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202140 KB Output is correct
2 Correct 90 ms 202264 KB Output is correct
3 Correct 102 ms 202172 KB Output is correct
4 Correct 90 ms 202220 KB Output is correct
5 Correct 91 ms 202224 KB Output is correct
6 Correct 91 ms 202132 KB Output is correct
7 Correct 95 ms 202188 KB Output is correct
8 Correct 92 ms 202168 KB Output is correct
9 Correct 92 ms 202356 KB Output is correct
10 Correct 103 ms 202572 KB Output is correct
11 Correct 97 ms 202328 KB Output is correct
12 Correct 90 ms 202500 KB Output is correct
13 Correct 88 ms 202248 KB Output is correct
14 Correct 91 ms 202484 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202140 KB Output is correct
2 Correct 90 ms 202264 KB Output is correct
3 Correct 102 ms 202172 KB Output is correct
4 Correct 90 ms 202220 KB Output is correct
5 Correct 91 ms 202224 KB Output is correct
6 Correct 91 ms 202132 KB Output is correct
7 Correct 95 ms 202188 KB Output is correct
8 Correct 92 ms 202168 KB Output is correct
9 Correct 92 ms 202356 KB Output is correct
10 Correct 103 ms 202572 KB Output is correct
11 Correct 97 ms 202328 KB Output is correct
12 Correct 90 ms 202500 KB Output is correct
13 Correct 88 ms 202248 KB Output is correct
14 Correct 91 ms 202484 KB Output is correct
15 Correct 88 ms 202372 KB Output is correct
16 Correct 90 ms 202444 KB Output is correct
17 Correct 224 ms 206860 KB Output is correct
18 Correct 245 ms 207004 KB Output is correct
19 Correct 178 ms 206932 KB Output is correct
20 Correct 176 ms 207028 KB Output is correct
21 Correct 177 ms 207024 KB Output is correct
22 Correct 405 ms 211568 KB Output is correct
23 Correct 98 ms 203376 KB Output is correct
24 Correct 134 ms 205388 KB Output is correct
25 Incorrect 94 ms 202496 KB 1st lines differ - on the 1st token, expected: '443843838929', found: '443838673362'
26 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202140 KB Output is correct
2 Correct 90 ms 202264 KB Output is correct
3 Correct 102 ms 202172 KB Output is correct
4 Correct 90 ms 202220 KB Output is correct
5 Correct 91 ms 202224 KB Output is correct
6 Correct 91 ms 202132 KB Output is correct
7 Correct 95 ms 202188 KB Output is correct
8 Correct 92 ms 202168 KB Output is correct
9 Correct 92 ms 202356 KB Output is correct
10 Correct 103 ms 202572 KB Output is correct
11 Correct 97 ms 202328 KB Output is correct
12 Correct 90 ms 202500 KB Output is correct
13 Correct 88 ms 202248 KB Output is correct
14 Correct 91 ms 202484 KB Output is correct
15 Correct 88 ms 202372 KB Output is correct
16 Correct 90 ms 202444 KB Output is correct
17 Correct 224 ms 206860 KB Output is correct
18 Correct 245 ms 207004 KB Output is correct
19 Correct 178 ms 206932 KB Output is correct
20 Correct 176 ms 207028 KB Output is correct
21 Correct 177 ms 207024 KB Output is correct
22 Correct 405 ms 211568 KB Output is correct
23 Correct 98 ms 203376 KB Output is correct
24 Correct 134 ms 205388 KB Output is correct
25 Incorrect 94 ms 202496 KB 1st lines differ - on the 1st token, expected: '443843838929', found: '443838673362'
26 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 248920 KB Output is correct
2 Correct 159 ms 248880 KB Output is correct
3 Correct 175 ms 246400 KB Output is correct
4 Correct 180 ms 249908 KB Output is correct
5 Correct 208 ms 251304 KB Output is correct
6 Correct 205 ms 251364 KB Output is correct
7 Correct 213 ms 251592 KB Output is correct
8 Correct 204 ms 251376 KB Output is correct
9 Correct 208 ms 252512 KB Output is correct
10 Correct 164 ms 230640 KB Output is correct
11 Correct 255 ms 259140 KB Output is correct
12 Correct 91 ms 202144 KB Output is correct
13 Correct 92 ms 202260 KB Output is correct
14 Correct 90 ms 202200 KB Output is correct
15 Correct 90 ms 202152 KB Output is correct
16 Correct 96 ms 202264 KB Output is correct
17 Correct 92 ms 202176 KB Output is correct
18 Correct 159 ms 248924 KB Output is correct
19 Correct 164 ms 248820 KB Output is correct
20 Correct 169 ms 248900 KB Output is correct
21 Correct 163 ms 248816 KB Output is correct
22 Incorrect 212 ms 253900 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45482472062250'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 252008 KB Output is correct
2 Correct 188 ms 260076 KB Output is correct
3 Correct 154 ms 248840 KB Output is correct
4 Correct 160 ms 248964 KB Output is correct
5 Correct 286 ms 279828 KB Output is correct
6 Correct 366 ms 279836 KB Output is correct
7 Correct 89 ms 202256 KB Output is correct
8 Execution timed out 1087 ms 259664 KB Time limit exceeded
9 Halted 0 ms 0 KB -