oj.uz

Submission #1110976

# Submission time Handle Problem Language Result Execution time Memory
1110976 2024-11-11T08:19:16 Z jerzyk Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 201412 KB 
#include <bits/stdc++.h>
#include "fish.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
vector<pair<int, ll>> cat[N];
vector<int> dpv[N];
vector<ll> dp[N][2], sl[N], as[N], sr[N];

void CntS(int n)
{
    for(int l = 0; l <= n; ++l)
    {
        int j1 = 0, j2 = 0, j3 = 0, s1 = 0, s2 = 0, s3 = 0;
        //cerr << l << " " << dpv[l].size() << " " << as[l].size() << "\n";
        for(int i = 1; i < (int)dpv[l].size(); ++i)
        {
            while(l > 0 && j1 < (int)cat[l - 1].size() - 1 && cat[l - 1][j1 + 1].st <= dpv[l][i])
            {
                ++j1;
                s1 += cat[l - 1][j1].nd;
            }
            while(j2 < (int)cat[l].size() - 1 && cat[l][j2 + 1].st <= dpv[l][i])
            {
                ++j2;
                s2 += cat[l][j2].nd;
            }
            while(j3 < (int)cat[l + 1].size() - 1 && cat[l + 1][j3 + 1].st <= dpv[l][i])
            {
                ++j3;
                s3 += cat[l + 1][j3].nd;
            }
            //cerr << i << " ";
            sl[l][i] = s1; as[l][i] = s2; sr[l][i] = s3;
        }
    }
}

void Do1()
{
    for(int i = 1; i < (int)dpv[1].size(); ++i)
    {
        dp[1][0][i] = sr[1][i];
        //dp[1][2][i] = sr[1][i];
    }
}

void CntDP(int n)
{
    Do1();
    for(int l = 2; l <= n; ++l)
    {
        for(int i = 1; i < (int)dpv[l].size(); ++i)
        {
            for(int j = 0; j < (int)dpv[l - 2].size(); ++j)
            {
                if(dpv[l - 2][j] <= dpv[l][i])
                    dp[l][0][i] = max(dp[l][0][i], dp[l - 2][0][j] - sr[l - 2][j] + sl[l][i]);
                else
                    dp[l][0][i] = max(dp[l][0][i], dp[l - 2][0][j]);
            }
            dp[l][1][i] = dp[l][0][i];
            for(int j = 0; j < (int)dpv[l - 1].size(); ++j)
            {
                if(dpv[l - 1][j] <= dpv[l][i])
                    dp[l][1][i] = max(dp[l][1][i], dp[l - 1][1][j] + sl[l][i] - as[l - 1][j]);
                if(dpv[l - 1][j] >= dpv[l][i])
                    dp[l][0][i] = max(dp[l][0][i], dp[l - 1][0][j] - as[l][i]);
            }
            dp[l][0][i] = max(dp[l][0][i], dp[l][1][i]) + sr[l][i];
            //cerr << l << " " << i << " " << dp[l][0][i] << " " << dp[l][1][i] << "\n";
        }
    }
}

long long max_weights(int _N, int _M, vector<int> X, vector<int> Y, vector<int> W)
{
    int n = _N, m = _M;
    for(int i = 0; i < m; ++i)
        {X[i] += 1; Y[i] += 1;}
    for(int i = 0; i <= n + 1; ++i)
    {
        dpv[i].pb(0);
        cat[i].pb(make_pair(0, 0LL));
    }
    for(int i = 0; i < m; ++i)
    {
        cat[X[i]].pb(make_pair(Y[i], W[i]));
        if(X[i] > 1)
            dpv[X[i] - 1].pb(Y[i]);
        if(X[i] < N)
            dpv[X[i] + 1].pb(Y[i]);
    }
    for(int l = 0; l <= n; ++l)
    {
        sort(cat[l].begin(), cat[l].end());
        sort(dpv[l].begin(), dpv[l].end());
        vector<int> nw;
        for(int i = 0; i < (int)dpv[l].size(); ++i)
            if(i == 0 || dpv[l][i] != dpv[l][i - 1])
                nw.pb(dpv[l][i]);
        dpv[l] = nw;
        for(int i = 0; i < (int)dpv[l].size(); ++i)
            dp[l][0].pb(0);
        dp[l][1] = dp[l][0];
        sl[l] = dp[l][0]; as[l] = dp[l][0]; sr[l] = dp[l][0];
    }
    CntS(n);
    CntDP(n);
    //cerr << "XD\n";
    ll ans = 0LL;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < (int)dpv[i].size(); ++j)
            ans = max(ans, dp[i][0][j]);
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 164760 KB Output is correct
2 Execution timed out 1087 ms 201412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 186616 KB Output is correct
2 Correct 117 ms 186696 KB Output is correct
3 Incorrect 167 ms 186692 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '285065011378'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 164624 KB Output is correct
2 Correct 110 ms 164696 KB Output is correct
3 Correct 102 ms 164796 KB Output is correct
4 Correct 91 ms 164764 KB Output is correct
5 Correct 103 ms 164700 KB Output is correct
6 Correct 98 ms 164804 KB Output is correct
7 Correct 90 ms 164680 KB Output is correct
8 Correct 119 ms 164680 KB Output is correct
9 Incorrect 93 ms 164680 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '150416253857'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 164624 KB Output is correct
2 Correct 110 ms 164696 KB Output is correct
3 Correct 102 ms 164796 KB Output is correct
4 Correct 91 ms 164764 KB Output is correct
5 Correct 103 ms 164700 KB Output is correct
6 Correct 98 ms 164804 KB Output is correct
7 Correct 90 ms 164680 KB Output is correct
8 Correct 119 ms 164680 KB Output is correct
9 Incorrect 93 ms 164680 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '150416253857'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 164624 KB Output is correct
2 Correct 110 ms 164696 KB Output is correct
3 Correct 102 ms 164796 KB Output is correct
4 Correct 91 ms 164764 KB Output is correct
5 Correct 103 ms 164700 KB Output is correct
6 Correct 98 ms 164804 KB Output is correct
7 Correct 90 ms 164680 KB Output is correct
8 Correct 119 ms 164680 KB Output is correct
9 Incorrect 93 ms 164680 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '150416253857'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 186616 KB Output is correct
2 Correct 117 ms 186696 KB Output is correct
3 Incorrect 167 ms 186692 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '285065011378'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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