oj.uz

Submission #1055695

# Submission time Handle Problem Language Result Execution time Memory
1055695 2024-08-13T03:38:39 Z vjudge1 Catfish Farm (IOI22_fish) C++17
0 / 100
 595 ms 445004 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int>fishies[3002];
ll FIS2;
ll dp[3010][2][3010],fishiess[3010][3010];
ll first[3010][3010];
ll sec[3010][301],third[3010][3010],overal[3010][3010];
inline ll ones(int col,int len){
    return fishiess[col][len];
}
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
    for(int i=0;i<M;i++)
        fishies[X[i]+1].insert(Y[i]+1),
        fishiess[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N+1;j++)
            fishiess[i][j]+=fishiess[i][j-1];
    for(int i=1;i<=N;i++)
        fishies[i].insert(1),
        fishies[i].insert(N+1);
    fishies[N+1].insert(0);
    for(auto i:fishies[1])
        dp[1][1][i-1]=ones(2,i-1);
    for(int j=0;j<=N;j++){
        overal[1][j]=first[1][j]=max(dp[1][0][j],dp[1][1][j]);
        first[1][j]+=ones(2,j);sec[1][j]=dp[1][0][j];
        third[1][j]=dp[1][1][j]-ones(1,j)-ones(2,j);
    }
    for(int j=N;~j;j--)
        overal[1][j]=max(overal[1][j],overal[1][j+1]),
        sec[1][j]=max(sec[1][j],sec[1][j+1]);
    for(int j=1;j<=N;j++)
        first[1][j]=max(first[1][j],first[1][j-1]),
        third[1][j]=max(third[1][j],third[1][j-1]);
    for(int i=2;i<=N;i++){
        for(auto rw:fishies[i]) {
            ll cons=ones(i+1,rw-1)+ones(i-1,rw-1);
            dp[i][1][rw-1]=cons+max(first[i-2][rw-1],overal[i-2][rw]-ones(i-1,rw-1));
        }
        for(auto rw2:fishies[i])
            dp[i][0][rw2-1]=max(0ll,ones(i+1,rw2-1)-ones(i,rw2-1)+sec[i-1][rw2]);
        for(auto rw2:fishies[i]){
            ll cons=ones(i+1,rw2-1)+ones(i-1,rw2-1);
            dp[i][1][rw2-1]=third[i-1][rw2]+cons;
            dp[i][0][rw2-1]=max(dp[i][0][rw2-1],overal[i-1][rw2]-ones(i,rw2-1)-ones(i-1,rw2-1))+cons;
        }
        for(int j=0;j<=N;j++){
            overal[i][j]=first[i][j]=max(dp[i][0][j],dp[i][1][j]);
            first[i][j]-=ones(i+1,j);sec[i][j]=dp[i][0][j];
            third[i][j]=dp[i][1][j]-ones(i,j)-ones(i+1,j);
        }
        for(int j=N;~j;j--)
            overal[i][j]=max(overal[i][j],overal[i][j+1]),
            sec[i][j]=max(sec[i][j],sec[i][j+1]);
        for(int j=1;j<=N;j++)
            first[i][j]=max(first[i][j],first[i][j-1]),
            third[i][j]=max(third[i][j],third[i][j-1]);
    }
    return overal[N][0];
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 576 ms 445004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 595 ms 432164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 595 ms 432164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 576 ms 445004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -