oj.uz

Submission #657518

# Submission time Handle Problem Language Result Execution time Memory
657518 2022-11-10T02:17:35 Z sentheta Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 98252 KB 
#include "fish.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

#define rand() (uniform_int_distribution<int>(0,1<<30)(rng))
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const Int N = 2e5+5;

Int n, m;
V<Int> x, y, w;

V<pii> g[N];
Int dp[N][10][10];

Int max_weights(int _n,int _m,V<int> _x,V<int> _y,V<int> _w){
	n = _n; m = _m;
	x = V<Int>(all(_x)); y = V<Int>(all(_y)); w = V<Int>(all(_w));

	rep(i,0,m){
		g[x[i]].push_back({y[i], w[i]});
		// dbg(x[i]);
		// c[x[i]] = w[i];
	}
	rep(i,0,n){
		sort(all(g[i]));
		g[i].push_back({n, 0});

		// dbg(i);
		// for(auto[j,k] : g[i]) cout << j _ k << nl;
	}
	// cout << nl;

	rep(i,1,n){
		// dbg(i);

		rep(p,0,i==1 ? 1:g[i-2].size()) rep(q,0,g[i-1].size())
		rep(r,0,g[i].size()){
			Int cost = dp[i-1][p][q];

			int pp = i==1 ? 0:g[i-2][p].ff;
			int qq = g[i-1][q].ff;
			int rr = g[i][r].ff;
			// dbg(pp); dbg(qq); dbg(rr);

			rep(j,q,g[i-1].size())
			if(pp-1<g[i-1][j].ff && g[i-1][j].ff<=rr-1){
				cost += g[i-1][j].ss;
			}

			rep(j,r,g[i].size())
			if(g[i][j].ff <= qq-1){
				cost += g[i][j].ss;
			}
			// dbg(cost);
			// cout << nl;

			dp[i][q][r] = max(dp[i][q][r], cost);
		}
	}

	// dbg(dp[1][0][0]);
	// dbg(dp[1][0][1]);
	// dbg(dp[1][1][0]);
	// dbg(dp[1][1][1]);

	Int ans = 0;
	rep(p,0,g[n-2].size()) rep(q,0,g[n-1].size()){
		ans = max(ans, dp[n-1][p][q]);
	}
	return ans;




	return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 14408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1096 ms 16876 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 86356 KB Output is correct
2 Correct 45 ms 86376 KB Output is correct
3 Correct 64 ms 80844 KB Output is correct
4 Correct 61 ms 88004 KB Output is correct
5 Correct 91 ms 91032 KB Output is correct
6 Correct 85 ms 91116 KB Output is correct
7 Correct 89 ms 91096 KB Output is correct
8 Correct 89 ms 91084 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 8 ms 5332 KB Output is correct
11 Correct 4 ms 5144 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 4 ms 5272 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 8 ms 5332 KB Output is correct
11 Correct 4 ms 5144 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 4 ms 5272 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Incorrect 523 ms 5188 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '147924879044256'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 8 ms 5332 KB Output is correct
11 Correct 4 ms 5144 KB Output is correct
12 Correct 4 ms 5332 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 4 ms 5272 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Incorrect 523 ms 5188 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '147924879044256'
17 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 86356 KB Output is correct
2 Correct 45 ms 86376 KB Output is correct
3 Correct 64 ms 80844 KB Output is correct
4 Correct 61 ms 88004 KB Output is correct
5 Correct 91 ms 91032 KB Output is correct
6 Correct 85 ms 91116 KB Output is correct
7 Correct 89 ms 91096 KB Output is correct
8 Correct 89 ms 91084 KB Output is correct
9 Correct 95 ms 91052 KB Output is correct
10 Correct 69 ms 51644 KB Output is correct
11 Correct 138 ms 98188 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 50 ms 86392 KB Output is correct
19 Correct 47 ms 86348 KB Output is correct
20 Correct 48 ms 86348 KB Output is correct
21 Correct 47 ms 86304 KB Output is correct
22 Correct 110 ms 91552 KB Output is correct
23 Correct 140 ms 98248 KB Output is correct
24 Correct 145 ms 98252 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 14408 KB Time limit exceeded
2 Halted 0 ms 0 KB -