oj.uz

Submission #837955

# Submission time Handle Problem Language Result Execution time Memory
837955 2023-08-25T21:27:54 Z JakobZorz Catfish Farm (IOI22_fish) C++17
47 / 100
 1000 ms 277208 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=LLONG_MIN;
    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=LLONG_MIN;
    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=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=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 175 ms 251840 KB Output is correct
2 Correct 181 ms 258260 KB Output is correct
3 Correct 164 ms 248876 KB Output is correct
4 Correct 157 ms 248884 KB Output is correct
5 Correct 284 ms 277208 KB Output is correct
6 Correct 367 ms 273064 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 202188 KB Output is correct
2 Execution timed out 1088 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 156 ms 248848 KB Output is correct
2 Correct 152 ms 248844 KB Output is correct
3 Correct 176 ms 245508 KB Output is correct
4 Correct 172 ms 249732 KB Output is correct
5 Correct 223 ms 251436 KB Output is correct
6 Correct 200 ms 251272 KB Output is correct
7 Correct 218 ms 251208 KB Output is correct
8 Correct 209 ms 251244 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202260 KB Output is correct
2 Correct 88 ms 202208 KB Output is correct
3 Correct 89 ms 202212 KB Output is correct
4 Correct 88 ms 202184 KB Output is correct
5 Correct 90 ms 202176 KB Output is correct
6 Correct 98 ms 202156 KB Output is correct
7 Correct 90 ms 202184 KB Output is correct
8 Correct 89 ms 202256 KB Output is correct
9 Correct 88 ms 202352 KB Output is correct
10 Correct 89 ms 202504 KB Output is correct
11 Correct 107 ms 202316 KB Output is correct
12 Correct 88 ms 202424 KB Output is correct
13 Correct 87 ms 202288 KB Output is correct
14 Correct 89 ms 202344 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202260 KB Output is correct
2 Correct 88 ms 202208 KB Output is correct
3 Correct 89 ms 202212 KB Output is correct
4 Correct 88 ms 202184 KB Output is correct
5 Correct 90 ms 202176 KB Output is correct
6 Correct 98 ms 202156 KB Output is correct
7 Correct 90 ms 202184 KB Output is correct
8 Correct 89 ms 202256 KB Output is correct
9 Correct 88 ms 202352 KB Output is correct
10 Correct 89 ms 202504 KB Output is correct
11 Correct 107 ms 202316 KB Output is correct
12 Correct 88 ms 202424 KB Output is correct
13 Correct 87 ms 202288 KB Output is correct
14 Correct 89 ms 202344 KB Output is correct
15 Correct 88 ms 202348 KB Output is correct
16 Correct 95 ms 202456 KB Output is correct
17 Correct 209 ms 206740 KB Output is correct
18 Correct 239 ms 206840 KB Output is correct
19 Correct 175 ms 206924 KB Output is correct
20 Correct 178 ms 206860 KB Output is correct
21 Correct 176 ms 207040 KB Output is correct
22 Correct 430 ms 211408 KB Output is correct
23 Correct 95 ms 203240 KB Output is correct
24 Correct 133 ms 205248 KB Output is correct
25 Correct 89 ms 202372 KB Output is correct
26 Correct 101 ms 203212 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 202260 KB Output is correct
2 Correct 88 ms 202208 KB Output is correct
3 Correct 89 ms 202212 KB Output is correct
4 Correct 88 ms 202184 KB Output is correct
5 Correct 90 ms 202176 KB Output is correct
6 Correct 98 ms 202156 KB Output is correct
7 Correct 90 ms 202184 KB Output is correct
8 Correct 89 ms 202256 KB Output is correct
9 Correct 88 ms 202352 KB Output is correct
10 Correct 89 ms 202504 KB Output is correct
11 Correct 107 ms 202316 KB Output is correct
12 Correct 88 ms 202424 KB Output is correct
13 Correct 87 ms 202288 KB Output is correct
14 Correct 89 ms 202344 KB Output is correct
15 Correct 88 ms 202348 KB Output is correct
16 Correct 95 ms 202456 KB Output is correct
17 Correct 209 ms 206740 KB Output is correct
18 Correct 239 ms 206840 KB Output is correct
19 Correct 175 ms 206924 KB Output is correct
20 Correct 178 ms 206860 KB Output is correct
21 Correct 176 ms 207040 KB Output is correct
22 Correct 430 ms 211408 KB Output is correct
23 Correct 95 ms 203240 KB Output is correct
24 Correct 133 ms 205248 KB Output is correct
25 Correct 89 ms 202372 KB Output is correct
26 Correct 101 ms 203212 KB Output is correct
27 Correct 91 ms 203728 KB Output is correct
28 Execution timed out 1105 ms 224124 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 248848 KB Output is correct
2 Correct 152 ms 248844 KB Output is correct
3 Correct 176 ms 245508 KB Output is correct
4 Correct 172 ms 249732 KB Output is correct
5 Correct 223 ms 251436 KB Output is correct
6 Correct 200 ms 251272 KB Output is correct
7 Correct 218 ms 251208 KB Output is correct
8 Correct 209 ms 251244 KB Output is correct
9 Correct 206 ms 251276 KB Output is correct
10 Correct 162 ms 228900 KB Output is correct
11 Correct 257 ms 255832 KB Output is correct
12 Correct 88 ms 202256 KB Output is correct
13 Correct 89 ms 202252 KB Output is correct
14 Correct 92 ms 202216 KB Output is correct
15 Correct 87 ms 202224 KB Output is correct
16 Correct 92 ms 202296 KB Output is correct
17 Correct 88 ms 202140 KB Output is correct
18 Correct 148 ms 248792 KB Output is correct
19 Correct 158 ms 248840 KB Output is correct
20 Correct 154 ms 248884 KB Output is correct
21 Correct 151 ms 248884 KB Output is correct
22 Incorrect 215 ms 251724 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 175 ms 251840 KB Output is correct
2 Correct 181 ms 258260 KB Output is correct
3 Correct 164 ms 248876 KB Output is correct
4 Correct 157 ms 248884 KB Output is correct
5 Correct 284 ms 277208 KB Output is correct
6 Correct 367 ms 273064 KB Output is correct
7 Correct 90 ms 202188 KB Output is correct
8 Execution timed out 1088 ms 259480 KB Time limit exceeded
9 Halted 0 ms 0 KB -