Submission #677119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
677119	2023-01-02T10:18:06 Z	Ninja_Kunai	Catfish Farm (IOI22_fish)	C++17	18 / 100	93 ms	14480 KB

fish

/**
*    Author :  Nguyen Tuan Vu
*    Created : 01.01.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}

const int N = 1e5 + 5;
namespace sub1 {
	bool check(int m, vector <array <int, 3>> fishes) {
		REP(i, m) {
			if (fishes[i][0] & 1) return false;
		}

		return true;
	}

	long long solve(int m, vector <array <int, 3>> fishes) {
		//assert(1 == 0);
		long long ans = 0;
		REP(i, m) ans += fishes[i][2];
		return ans;
	}
}

namespace sub2 {
	bool check(int m, vector <array <int, 3>> fishes) {
		REP(i, m) if (fishes[i][0] > 1) return false;
		return true;
	}

	long long solve(int n, int m, vector <array <int, 3>> fishes) {
		//assert(1 == 0);
		if (n == 2) {
			long long ans[2] = {0};
			REP(i, m) ans[fishes[i][0]] += fishes[i][2];
			return max(ans[0], ans[1]);
		}

		vector <long long> sum[2];
		REP(i, 2) sum[i].resize(n + 7, 0);
		REP(i, m) sum[fishes[i][0]][fishes[i][1]] += fishes[i][2];
		FOR(i, 1, n - 1) REP(j, 2) sum[j][i] = sum[j][i - 1] + sum[j][i];
		long long ans = sum[1][n - 1];
		REP(i, n) maximize(ans, sum[0][i] + sum[1][n - 1] - sum[1][i]);
		return ans;
	}
}

namespace sub3 {
    bool check(int m, vector <array <int, 3>> fishes) {
        REP(i, m) if (fishes[i][1] != 0) return false;
        return true;
    }

    int cost[N];
    long long dp[N];

    long long solve(int n, int m, vector <array <int, 3>> fishes) {
        REP(i, m) cost[fishes[i][0] + 1] = fishes[i][2];
        //FOR(i, 1, n) cout << cost[i] << " \n"[i == n];
        FOR(i, 1, n) {
            maximize(dp[i], dp[i - 1]);
            if (i >= 2) maximize(dp[i], dp[i - 2] + cost[i - 1]);
            if (i > 3) maximize(dp[i], dp[i - 3] + cost[i - 1] + cost[i - 2]);

            //cout << dp[i] << " \n"[i == n];
        }

        long long ans = 0;
        FOR(i, 1, n) {
            dp[i] = dp[i] + cost[i + 1];
            maximize(ans, dp[i]);
        }

        return ans;
    }
}

long long max_weights(int n, int m, vector <int> X, vector <int> Y, vector <int> W) {
	vector <array <int, 3>> fishes;
	fishes.resize(m + 7);
	REP(i, m) fishes[i] = {X[i], Y[i], W[i]};

	if (sub1::check(m, fishes)) return sub1::solve(m, fishes);
	else if (sub2::check(m, fishes)) return sub2::solve(n, m, fishes);
	else if (sub3::check(m, fishes)) return sub3::solve(n, m, fishes);
	return 0;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	4172 KB	Output is correct
2	Correct	27 ms	5072 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	93 ms	14416 KB	Output is correct
6	Correct	90 ms	14480 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	54 ms	9344 KB	Output is correct
3	Correct	61 ms	11252 KB	Output is correct
4	Correct	22 ms	4172 KB	Output is correct
5	Correct	29 ms	5008 KB	Output is correct
6	Correct	1 ms	308 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	25 ms	5508 KB	Output is correct
13	Correct	30 ms	6720 KB	Output is correct
14	Correct	24 ms	5504 KB	Output is correct
15	Correct	28 ms	6152 KB	Output is correct
16	Correct	25 ms	5524 KB	Output is correct
17	Correct	28 ms	6144 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	980 KB	Output is correct
3	Correct	15 ms	3984 KB	Output is correct
4	Correct	11 ms	3640 KB	Output is correct
5	Correct	29 ms	7724 KB	Output is correct
6	Correct	26 ms	7076 KB	Output is correct
7	Correct	27 ms	7624 KB	Output is correct
8	Correct	30 ms	7684 KB	Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	980 KB	Output is correct
3	Correct	15 ms	3984 KB	Output is correct
4	Correct	11 ms	3640 KB	Output is correct
5	Correct	29 ms	7724 KB	Output is correct
6	Correct	26 ms	7076 KB	Output is correct
7	Correct	27 ms	7624 KB	Output is correct
8	Correct	30 ms	7684 KB	Output is correct
9	Incorrect	24 ms	6320 KB	1st lines differ - on the 1st token, expected: '99999', found: '0'
10	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	4172 KB	Output is correct
2	Correct	27 ms	5072 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	93 ms	14416 KB	Output is correct
6	Correct	90 ms	14480 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	54 ms	9344 KB	Output is correct
9	Correct	61 ms	11252 KB	Output is correct
10	Correct	22 ms	4172 KB	Output is correct
11	Correct	29 ms	5008 KB	Output is correct
12	Correct	1 ms	308 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	25 ms	5508 KB	Output is correct
19	Correct	30 ms	6720 KB	Output is correct
20	Correct	24 ms	5504 KB	Output is correct
21	Correct	28 ms	6152 KB	Output is correct
22	Correct	25 ms	5524 KB	Output is correct
23	Correct	28 ms	6144 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	980 KB	Output is correct
26	Correct	15 ms	3984 KB	Output is correct
27	Correct	11 ms	3640 KB	Output is correct
28	Correct	29 ms	7724 KB	Output is correct
29	Correct	26 ms	7076 KB	Output is correct
30	Correct	27 ms	7624 KB	Output is correct
31	Correct	30 ms	7684 KB	Output is correct
32	Incorrect	1 ms	212 KB	1st lines differ - on the 1st token, expected: '3', found: '0'
33	Halted	0 ms	0 KB	-

Submission #677119

Compilation message