Submission #947155

#	Time	Username	Problem	Language	Result	Execution time	Memory
947155		Nhoksocqt1	메기 농장 (IOI22_fish)	C++17	70 / 100	886 ms	912568 KiB

fish

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

struct Fish {
    int x, y, w;
} fish[3 * MAXN];

ll f[303][303][303], maxPre[3003][303], maxSuf[3003][303];
ll dp[3003][3003], dp2[3003][3003], sum[3003][3003];
int val[MAXN], nSize, numFish;

ll sub1(void) {
    ll sum(0);
    for (int i = 0; i < numFish; ++i)
        sum += fish[i].w;

    return sum;
}

ll sub2(void) {
    ll ans(0), sum0(0), sum1(0);
    int j(numFish);
    for (int i = 0; i < numFish; ++i) {
        if(fish[i].x == 0) {
            sum0 += fish[i].w;
        } else {
            if(j == numFish)
                j = i;

            sum1 += fish[i].w;
        }
    }

    ans = max(sum0, sum1);
    if(nSize == 2)
        return ans;

    sum0 = 0;
    for (int i = 0; i < numFish; ++i) {
        if(fish[i].x == 1)
            break;

        sum0 += fish[i].w;
        while(j < numFish && fish[j].y <= fish[i].y) {
            sum1 -= fish[j].w;
            ++j;
        }

        ans = max(ans, sum0 + sum1);
    }

    return ans;
}

ll sub3(void) {
    for (int i = 0; i <= 1; ++i)
        dp[i][0] = dp[i][1] = dp[i][2] = -1e18;

    for (int i = 0; i < numFish; ++i)
        val[fish[i].x] = fish[i].w;

    dp[0][2] = 0;
    for (int i = 0; i < nSize; ++i) {
        int pre(i & 1), cur(!pre);
        dp[cur][0] = max(dp[pre][0], max(dp[pre][1], dp[pre][2] + (i > 0 ? val[i - 1] : 0)));
        dp[cur][1] = dp[pre][0] + val[i];
        dp[cur][2] = max(dp[pre][2], dp[pre][1]);
    }

    return max({dp[nSize & 1][0], dp[nSize & 1][1], dp[nSize & 1][2]});
}

ll sub5(void) {
    for (int i = 0; i < nSize; ++i) {
        for (int j = 0; j <= nSize; ++j)
            sum[i][j] = 0;
    }

    for (int i = 0; i < numFish; ++i)
        sum[fish[i].x][fish[i].y + 1] += fish[i].w;

    for (int i = 0; i < nSize; ++i) {
        for (int j = 1; j <= nSize; ++j)
            sum[i][j] += sum[i][j - 1];
    }

    for (int j = 0; j <= nSize; ++j) {
        for (int k = 0; k <= nSize; ++k) {
            f[0][j][k] = -1e18;
        }
    }

    f[0][0][0] = 0;
    for (int j = 0; j <= nSize; ++j) {
        for (int k = 0; k <= nSize; ++k) {
            maxPre[j][k] = f[0][j][k];
            if(k > 0)
                maxPre[j][k] = max(maxPre[j][k], maxPre[j][k - 1]);
        }
    }

    for (int j = nSize; j >= 0; --j) {
        for (int k = nSize; k >= 0; --k) {
            maxSuf[j][k] = f[0][j][k];
            if(k + 1 < nSize)
                maxSuf[j][k] = max(maxSuf[j][k], maxSuf[j][k + 1]);
        }
    }

    for (int i = 0; i < nSize; ++i) {
        for (int coln = 0; coln <= nSize; ++coln) {
            for (int pcol = 0; pcol <= nSize; ++pcol) {
                if(coln <= pcol) {
                    f[i + 1][coln][pcol] = maxSuf[pcol][0] + sum[i][pcol] - sum[i][coln];
                    continue;
                }

                f[i + 1][coln][pcol] = maxPre[pcol][nSize] + (i > 0 ? sum[i - 1][coln] : 0);
                f[i + 1][coln][pcol] = max(f[i + 1][coln][pcol], maxSuf[pcol][0]);
            }
        }

        for (int j = 0; j <= nSize; ++j) {
            for (int k = 0; k <= nSize; ++k) {
                maxPre[j][k] = f[i + 1][j][k] - sum[i][max(j, k)];
                if(k > 0)
                    maxPre[j][k] = max(maxPre[j][k], maxPre[j][k - 1]);
            }
        }

        for (int j = nSize; j >= 0; --j) {
            for (int k = nSize; k >= 0; --k) {
                maxSuf[j][k] = f[i + 1][j][k];
                if(k < nSize)
                    maxSuf[j][k] = max(maxSuf[j][k], maxSuf[j][k + 1]);
            }
        }
    }

    ll res(0);
    for (int j = 0; j <= nSize; ++j)
        res = max(res, maxSuf[j][0]);

    return res;
}

ll sub6(void) {
    for (int i = 0; i <= nSize; ++i) {
        for (int j = 0; j <= nSize; ++j)
            sum[i][j] = 0;
    }

    for (int i = 0; i < numFish; ++i)
        sum[fish[i].x][fish[i].y + 1] += fish[i].w;

    for (int i = 0; i < nSize; ++i) {
        for (int j = 1; j <= nSize; ++j)
            sum[i][j] += sum[i][j - 1];
    }

    for (int j = 0; j <= nSize; ++j)
        dp[0][j] = dp2[0][j] = -1e18;

    dp[0][0] = dp2[0][0] = 0;
    for (int j = 0; j <= nSize; ++j) {
        ll val = dp2[0][j];
        maxPre[j][0] = (j == 0) ? val : max(maxPre[j - 1][0], val);
    }

    for (int j = nSize; j >= 0; --j) {
        ll val = dp[0][j] + sum[0][j];
        ll val2 = dp[0][j];
        maxSuf[j][0] = (j == nSize) ? val : max(maxSuf[j + 1][0], val);
        maxSuf[j][1] = (j == nSize) ? val2 : max(maxSuf[j + 1][1], val2);
    }

    for (int i = 0; i < nSize; ++i) {
        for (int coln = 0; coln <= nSize; ++coln) {
            dp[i + 1][coln] = maxSuf[coln][0] - sum[i][coln];
            dp[i + 1][coln] = max(dp[i + 1][coln], dp[i][coln]);
            dp[i + 1][coln] = max(dp[i + 1][coln], maxPre[coln][0] + (i > 0 ? sum[i - 1][coln] : 0));

            dp2[i + 1][coln] = maxPre[coln][0] + (i > 0 ? sum[i - 1][coln] : 0) - sum[i][coln];
            dp2[i + 1][coln] = max(dp2[i + 1][coln], maxSuf[coln][1]);
            dp2[i + 1][coln] = max(dp2[i + 1][coln], dp[i][coln] - sum[i][coln]);
        }

        for (int j = 0; j <= nSize; ++j) {
            ll val = dp2[i + 1][j];
            maxPre[j][0] = (j == 0) ? val : max(maxPre[j - 1][0], val);
        }

        for (int j = nSize; j >= 0; --j) {
            ll val = dp[i + 1][j] + sum[i + 1][j];
            ll val2 = dp[i + 1][j];
            maxSuf[j][0] = (j == nSize) ? val : max(maxSuf[j + 1][0], val);
            maxSuf[j][1] = (j == nSize) ? val2 : max(maxSuf[j + 1][1], val2);
        }
    }

    ll res(0);
    for (int j = 0; j <= nSize; ++j)
        res = max(res, dp[nSize][j]);

    return res;
}

ll max_weights(int _N, int _M, vector<int> _X, vector<int> _Y, vector<int> _W) {
    nSize = _N, numFish = _M;

    bool check1(1), check2(1), check3(1);
    for (int i = 0; i < numFish; ++i) {
        fish[i] = {_X[i], _Y[i], _W[i]};
        check1 &= !(fish[i].x & 1);
        check2 &= (fish[i].x <= 1);
        check3 &= (fish[i].y == 0);
    }

    sort(fish, fish + numFish, [](const Fish &a, const Fish &b) {
        return (a.x != b.x) ? a.x < b.x : a.y < b.y;
    });

    if(check1) {
        return sub1();
    } else
        if(check2) {
            return sub2();
        } else
            if(check3) {
                return sub3();
            } else
                if(nSize <= 300) {
                    return sub5();
                } else
                    if(nSize <= 3000) {
                        return sub6();
                    }
}

#ifdef Nhoksocqt1

bool dx[3003][3003];

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "fish"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> _X, _Y, _W;
    int _N, _M;
    cin >> _N >> _M;

    _X.resize(_M), _Y.resize(_M), _W.resize(_M);
    for (int i = 0; i < _M; ++i) {
        cin >> _X[i] >> _Y[i] >> _W[i];
        do { _X[i] = Random(0, _N - 1), _Y[i] = Random(0, _N - 1), _W[i] = Random(1, 100); } while(dx[_X[i]][_Y[i]]); dx[_X[i]][_Y[i]] = 1; cout << _X[i] << ' ' << _Y[i] << ' ' << _W[i] << '\n';
    }

    ll ans = max_weights(_N, _M, _X, _Y, _W);
    cout << "ANSWER: " << ans << '\n';
    cout << "SUB6: " << sub6() << '\n';

    return 0;
}

#endif // Nhoksocqt1

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:257:1: warning: control reaches end of non-void function [-Wreturn-type]
  257 | }
      | ^

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16