Submission #812173

#	Time	Username	Problem	Language	Result	Execution time	Memory
812173		_martynas	Catfish Farm (IOI22_fish)	C++17	Compilation error	0 ms	0 KiB

fish

// #include "fish.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

using ll = long long;
using pii = pair<int, int>;

const ll inf = 1e16;

int n, m;
map<pii, ll> F;

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N, m = M;
    vector<vector<int>> pos(n);
    for(int i = 0; i < m; i++) {
        if(X[i] > 0) pos[X[i]-1].pb(Y[i]);
        if(X[i]+1 < n) pos[X[i]+1].pb(Y[i]);
        F[{X[i], Y[i]}] = W[i];
    }
    // printf("interesting positions:\n");
    // for(int i = 0; i < n; i++) {
    //     printf("i = %d\n", i);
    //     for(int j : pos[i]) {
    //         printf("(%d, %d) ", i, j);
    //     }
    //     printf("\n");
    // }
    vector<vector<ll>> dp[2]; // 0-inc, 1-dec
    dp[0] = dp[1] = vector<vector<ll>>(n);
    for(int k = 0; k < 2; k++) {
        for(int i = 0; i < n; i++) {
            dp[k][i] = vector<ll>(pos[i].size(), -inf);
        }
    }
    ll mx_with = 0, mx_wo = 0; // 'with' as in with the fishes on the right
    for(int i = 0; i < n; i++) {
        ll sum;
        mx_wo = max(mx_wo, mx_with);
        if(i > 1) for(int j = 0; j < (int)pos[i-2].size(); j++) {
            mx_wo = max(mx_wo, dp[0][i-2][j]);
            mx_wo = max(mx_wo, dp[1][i-2][j]);
        }
        sum = 0;
        if(i > 1) for(int j = 0; j < (int)pos[i-2].size(); j++) {
            sum += F[pii{i-1, pos[i][j]}];
            mx_with = max(mx_with, dp[0][i-2][j]+sum);
            mx_with = max(mx_with, dp[1][i-2][j]+sum);
        }
        // try starting a new seq
        sum = 0;
        for(int j = 0; j < (int)pos[i].size(); j++) {
            sum += F[pii{i-1, pos[i][j]}];
            dp[0][i][j] = max(dp[0][i][j], mx_wo+sum);
            dp[0][i][j] = max(dp[0][i][j], mx_with);
        }
        // inc to inc
        ll mx = -inf;
        if(i > 0) for(int j = 0, k = 0; j < (int)pos[i].size(); j++) {
            while(k < (int)pos[i-1].size() && pos[i-1][k] < pos[i][j]) {
                mx = max(mx, dp[0][i-1][k]);
                k++;
            }
            mx += F[pii{i-1, pos[i][j]}];
            dp[0][i][j] = max(dp[0][i][j], mx);
        }
        mx = -inf;
        // inc/dec to dec
        if(i > 0) for(int j = (int)pos[i].size()-1, k = (int)pos[i-1].size()-1;
            j >= 0; j--) {
            while(k >= 0 && pos[i-1][k] > pos[i][j]) {
                mx = max(mx, dp[0][i-1][k]);
                mx = max(mx, dp[1][i-1][k]);
                mx += F[pii{i, pos[i-1][k]}];
                k--;
            }
            dp[1][i][j] = max(dp[1][i][j], mx);
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ll sum = 0;
        for(int j = 0; j < (int)pos[i].size(); j++) {
            sum += F[pii{i+1, pos[i][j]}];
            ans = max(ans, dp[0][i][j]+sum);
            ans = max(ans, dp[1][i][j]+sum);
        }
    }
    //cout << ans << "!\n";
    return ans;
}

int main() {
    int N, M;
    vector<int> X, Y, W;
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int x, y, w; cin >> x >> y >> w;
        X.pb(x), Y.pb(y), W.pb(w);
    }
    max_weights(N, M, X, Y, W);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc29heRw.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6Oydmy.o:fish.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status