oj.uz

Submission #837937

# Submission time Handle Problem Language Result Execution time Memory
837937 2023-08-25T20:55:37 Z JakobZorz Catfish Farm (IOI22_fish) C++17
47 / 100
 1000 ms 277416 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;
        }
        
        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 228 ms 251924 KB Output is correct
2 Correct 218 ms 258320 KB Output is correct
3 Correct 168 ms 248916 KB Output is correct
4 Correct 170 ms 248916 KB Output is correct
5 Correct 316 ms 277416 KB Output is correct
6 Correct 370 ms 273100 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 202196 KB Output is correct
2 Execution timed out 1072 ms 259856 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 248916 KB Output is correct
2 Correct 166 ms 248796 KB Output is correct
3 Correct 183 ms 245456 KB Output is correct
4 Correct 191 ms 250208 KB Output is correct
5 Correct 214 ms 251592 KB Output is correct
6 Correct 214 ms 251656 KB Output is correct
7 Correct 222 ms 251620 KB Output is correct
8 Correct 260 ms 251668 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 202184 KB Output is correct
2 Correct 101 ms 202436 KB Output is correct
3 Correct 98 ms 202248 KB Output is correct
4 Correct 99 ms 202168 KB Output is correct
5 Correct 102 ms 202216 KB Output is correct
6 Correct 101 ms 202232 KB Output is correct
7 Correct 102 ms 202328 KB Output is correct
8 Correct 100 ms 202220 KB Output is correct
9 Correct 100 ms 202352 KB Output is correct
10 Correct 103 ms 202592 KB Output is correct
11 Correct 99 ms 202316 KB Output is correct
12 Correct 104 ms 202472 KB Output is correct
13 Correct 98 ms 202244 KB Output is correct
14 Correct 99 ms 202444 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 202184 KB Output is correct
2 Correct 101 ms 202436 KB Output is correct
3 Correct 98 ms 202248 KB Output is correct
4 Correct 99 ms 202168 KB Output is correct
5 Correct 102 ms 202216 KB Output is correct
6 Correct 101 ms 202232 KB Output is correct
7 Correct 102 ms 202328 KB Output is correct
8 Correct 100 ms 202220 KB Output is correct
9 Correct 100 ms 202352 KB Output is correct
10 Correct 103 ms 202592 KB Output is correct
11 Correct 99 ms 202316 KB Output is correct
12 Correct 104 ms 202472 KB Output is correct
13 Correct 98 ms 202244 KB Output is correct
14 Correct 99 ms 202444 KB Output is correct
15 Correct 98 ms 202340 KB Output is correct
16 Correct 99 ms 202444 KB Output is correct
17 Correct 225 ms 207160 KB Output is correct
18 Correct 238 ms 207328 KB Output is correct
19 Correct 184 ms 207180 KB Output is correct
20 Correct 189 ms 207212 KB Output is correct
21 Correct 187 ms 207236 KB Output is correct
22 Correct 421 ms 211888 KB Output is correct
23 Correct 106 ms 203264 KB Output is correct
24 Correct 143 ms 205576 KB Output is correct
25 Correct 116 ms 202404 KB Output is correct
26 Correct 107 ms 203296 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 202184 KB Output is correct
2 Correct 101 ms 202436 KB Output is correct
3 Correct 98 ms 202248 KB Output is correct
4 Correct 99 ms 202168 KB Output is correct
5 Correct 102 ms 202216 KB Output is correct
6 Correct 101 ms 202232 KB Output is correct
7 Correct 102 ms 202328 KB Output is correct
8 Correct 100 ms 202220 KB Output is correct
9 Correct 100 ms 202352 KB Output is correct
10 Correct 103 ms 202592 KB Output is correct
11 Correct 99 ms 202316 KB Output is correct
12 Correct 104 ms 202472 KB Output is correct
13 Correct 98 ms 202244 KB Output is correct
14 Correct 99 ms 202444 KB Output is correct
15 Correct 98 ms 202340 KB Output is correct
16 Correct 99 ms 202444 KB Output is correct
17 Correct 225 ms 207160 KB Output is correct
18 Correct 238 ms 207328 KB Output is correct
19 Correct 184 ms 207180 KB Output is correct
20 Correct 189 ms 207212 KB Output is correct
21 Correct 187 ms 207236 KB Output is correct
22 Correct 421 ms 211888 KB Output is correct
23 Correct 106 ms 203264 KB Output is correct
24 Correct 143 ms 205576 KB Output is correct
25 Correct 116 ms 202404 KB Output is correct
26 Correct 107 ms 203296 KB Output is correct
27 Correct 101 ms 203812 KB Output is correct
28 Execution timed out 1061 ms 224792 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 248916 KB Output is correct
2 Correct 166 ms 248796 KB Output is correct
3 Correct 183 ms 245456 KB Output is correct
4 Correct 191 ms 250208 KB Output is correct
5 Correct 214 ms 251592 KB Output is correct
6 Correct 214 ms 251656 KB Output is correct
7 Correct 222 ms 251620 KB Output is correct
8 Correct 260 ms 251668 KB Output is correct
9 Correct 211 ms 251236 KB Output is correct
10 Correct 179 ms 228876 KB Output is correct
11 Correct 276 ms 255628 KB Output is correct
12 Correct 99 ms 202256 KB Output is correct
13 Correct 99 ms 202256 KB Output is correct
14 Correct 99 ms 202164 KB Output is correct
15 Correct 99 ms 202220 KB Output is correct
16 Correct 101 ms 202168 KB Output is correct
17 Correct 100 ms 202256 KB Output is correct
18 Correct 166 ms 248796 KB Output is correct
19 Correct 171 ms 248844 KB Output is correct
20 Correct 166 ms 248860 KB Output is correct
21 Correct 168 ms 248916 KB Output is correct
22 Incorrect 221 ms 251692 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 228 ms 251924 KB Output is correct
2 Correct 218 ms 258320 KB Output is correct
3 Correct 168 ms 248916 KB Output is correct
4 Correct 170 ms 248916 KB Output is correct
5 Correct 316 ms 277416 KB Output is correct
6 Correct 370 ms 273100 KB Output is correct
7 Correct 113 ms 202196 KB Output is correct
8 Execution timed out 1072 ms 259856 KB Time limit exceeded
9 Halted 0 ms 0 KB -