oj.uz

Submission #657517

# Submission time Handle Problem Language Result Execution time Memory
657517 2022-11-10T02:16:38 Z sentheta Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 74052 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][8][8];

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 1084 ms 13960 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 1071 ms 17800 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 58188 KB Output is correct
2 Correct 32 ms 58208 KB Output is correct
3 Correct 52 ms 55436 KB Output is correct
4 Correct 48 ms 59832 KB Output is correct
5 Correct 72 ms 62824 KB Output is correct
6 Correct 69 ms 62904 KB Output is correct
7 Correct 75 ms 62892 KB Output is correct
8 Correct 73 ms 62920 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5008 KB Output is correct
8 Correct 2 ms 5012 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Incorrect 8 ms 5332 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '1302537471574'
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5008 KB Output is correct
8 Correct 2 ms 5012 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Incorrect 8 ms 5332 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '1302537471574'
11 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 3 ms 5008 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5008 KB Output is correct
8 Correct 2 ms 5012 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Incorrect 8 ms 5332 KB 1st lines differ - on the 1st token, expected: '799839985182', found: '1302537471574'
11 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 58188 KB Output is correct
2 Correct 32 ms 58208 KB Output is correct
3 Correct 52 ms 55436 KB Output is correct
4 Correct 48 ms 59832 KB Output is correct
5 Correct 72 ms 62824 KB Output is correct
6 Correct 69 ms 62904 KB Output is correct
7 Correct 75 ms 62892 KB Output is correct
8 Correct 73 ms 62920 KB Output is correct
9 Correct 78 ms 62912 KB Output is correct
10 Correct 64 ms 39312 KB Output is correct
11 Correct 128 ms 73508 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5008 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5012 KB Output is correct
16 Correct 3 ms 5008 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 33 ms 58176 KB Output is correct
19 Correct 33 ms 58188 KB Output is correct
20 Correct 33 ms 58140 KB Output is correct
21 Correct 33 ms 58104 KB Output is correct
22 Correct 78 ms 65500 KB Output is correct
23 Correct 128 ms 73520 KB Output is correct
24 Correct 134 ms 74052 KB Output is correct

Subtask #8
0 / 16.0

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