oj.uz

Submission #940612

# Submission time Handle Problem Language Result Execution time Memory
940612 2024-03-07T11:38:17 Z Ghetto Catfish Farm (IOI22_fish) C++17
9 / 100
 31 ms 16952 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 1e5 + 5, MAX_M = 3e5 + 5;
const lint INF = 5e18;

int n, m;
int x[MAX_M], y[MAX_M];
lint w[MAX_M];

lint val[MAX_N];
void precomp() {
    for (int i = 0; i < m; i++)
        val[x[i]] = w[i];
}

lint dp[MAX_N];
bool seen[MAX_N];
lint find_dp(int i) {
    assert(i >= -1);
    if (i == -1) return 0;
    if (i == 0) return val[0];
    if (seen[i]) return dp[i];

    lint leave = find_dp(i - 1);
    lint leave_prev = val[i] + find_dp(i - 2);
    lint take_prev = (i == 1 || i == n - 1) ? -INF : val[i] + val[i - 1] + find_dp(i - 3);
    dp[i] = max({leave, leave_prev, take_prev});

    seen[i] = true;
    return dp[i];
}

void init() {
    for (int i = 0; i < n; i++) {
        seen[i] = false;
        dp[i] = -INF;
        val[i] = 0;
    }
}

lint max_weights(int tmp_n, int tmp_m, vector<int> tmp_x, vector<int> tmp_y, vector<int> tmp_w) {
    n = tmp_n; 
    m = tmp_m;
    init();
    for (int i = 0; i < m; i++) {
        x[i] = tmp_x[i];
        y[i] = tmp_y[i];
        w[i] = tmp_w[i];
    }

    precomp();

    lint ans = find_dp(n - 1);
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12896 KB Output is correct
2 Correct 8 ms 12916 KB Output is correct
3 Correct 23 ms 14280 KB Output is correct
4 Correct 15 ms 14428 KB Output is correct
5 Correct 31 ms 16912 KB Output is correct
6 Correct 24 ms 16208 KB Output is correct
7 Correct 29 ms 16728 KB Output is correct
8 Correct 30 ms 16952 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12896 KB Output is correct
2 Correct 8 ms 12916 KB Output is correct
3 Correct 23 ms 14280 KB Output is correct
4 Correct 15 ms 14428 KB Output is correct
5 Correct 31 ms 16912 KB Output is correct
6 Correct 24 ms 16208 KB Output is correct
7 Correct 29 ms 16728 KB Output is correct
8 Correct 30 ms 16952 KB Output is correct
9 Incorrect 27 ms 16724 KB 1st lines differ - on the 1st token, expected: '99999', found: '66666'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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