oj.uz

Submission #947082

# Submission time Handle Problem Language Result Execution time Memory
947082 2024-03-15T13:37:20 Z Nhoksocqt1 Catfish Farm (IOI22_fish) C++17
0 / 100
 128 ms 199256 KB 
#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[MAXN];

ll f[303][303][303];
int 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;

    sum1 = 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 <= numFish; ++i)
        f[i][0][0] = f[i][1][0] = -1e18;

    f[0][0][0] = 0;
    for (int i = 0; i < numFish; ++i) {
        f[i + 1][0][0] = max(f[i][0][0], f[i][1][0]);
        f[i + 1][1][0] = f[i][0][0] + fish[i].w;
    }

    return max(f[numFish][0][0], f[numFish][1][0]);
}

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();
            }
}

#ifdef Nhoksocqt1

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(_N), _Y.resize(_N), _W.resize(_N);
    for (int i = 0; i < _N; ++i)
        cin >> _X[i] >> _Y[i] >> _W[i];

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

    return 0;
}

#endif // Nhoksocqt1

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4592 KB Output is correct
2 Correct 30 ms 5580 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 81 ms 23476 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 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 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Runtime error 128 ms 199256 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 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 2396 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 2396 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 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Runtime error 128 ms 199256 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4592 KB Output is correct
2 Correct 30 ms 5580 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 81 ms 23476 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -