oj.uz

Submission #748267

# Submission time Handle Problem Language Result Execution time Memory
748267 2023-05-26T02:34:35 Z bachhoangxuan Catfish Farm (IOI22_fish) C++17
3 / 100
 191 ms 39116 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18;
struct fish{
    int y=0;
    ll cost,f0=0,f1=0;
    friend bool operator<(fish a,fish b){
        return a.y<b.y;
    }
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<vector<fish>> dp(N+1);
    vector<int> check(N+1,0);
    for(int i=0;i<M;i++){
        X[i]++;Y[i]++;
        dp[X[i]].push_back({Y[i]-1,W[i],0,0});
        check[X[i]]|=(Y[i]==1);
    }
    for(int i=0;i<=N;i++){
        if(!check[i]) dp[i].push_back({0,0,0,0});
        dp[i].push_back({N,0,0,0});
        sort(dp[i].begin(),dp[i].end());
    }
    for(auto &x:dp[0]) x.f0=x.f1=0;
    for(int i=1;i<=N;i++){
        int cur=0;
        ll sum=0,csum=0,Max=dp[i-1][0].f0;
        for(auto &a:dp[i]){
            csum+=a.cost;
            while(cur+1<(int)dp[i-1].size() && dp[i-1][cur+1].y<a.y){
                sum+=dp[i-1][cur].cost;cur++;
                Max=max(Max,dp[i-1][cur].f0-sum);
            }
            a.f0=Max+sum+dp[i-1][cur].cost;
        }
        Max=dp[i-1].back().f1+csum;
        for(int j=(int)dp[i].size()-1;j>=0;j--){
            auto &a=dp[i][j];
            while(cur && dp[i-1][cur-1].y>a.y){
                cur--,Max=max(Max,dp[i-1][cur].f1+csum);
            }
            csum-=a.cost;
            a.f1=Max-csum;
        }
        dp[i].front().f0=max(dp[i].front().f0,dp[i-1].front().f1);
        dp[i].back().f1=max({dp[i].back().f1,dp[i].back().f0,dp[i-1].front().f1});
    }
    return max(dp[N].front().f1,dp[N].back().f0);
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15132 KB Output is correct
2 Correct 72 ms 18096 KB Output is correct
3 Correct 14 ms 10848 KB Output is correct
4 Correct 15 ms 10764 KB Output is correct
5 Correct 166 ms 33624 KB Output is correct
6 Correct 191 ms 39116 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Incorrect 92 ms 20160 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10892 KB Output is correct
2 Correct 15 ms 10856 KB Output is correct
3 Incorrect 35 ms 12500 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 224 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 224 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 224 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10892 KB Output is correct
2 Correct 15 ms 10856 KB Output is correct
3 Incorrect 35 ms 12500 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15132 KB Output is correct
2 Correct 72 ms 18096 KB Output is correct
3 Correct 14 ms 10848 KB Output is correct
4 Correct 15 ms 10764 KB Output is correct
5 Correct 166 ms 33624 KB Output is correct
6 Correct 191 ms 39116 KB Output is correct
7 Correct 1 ms 224 KB Output is correct
8 Incorrect 92 ms 20160 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
9 Halted 0 ms 0 KB -