답안 #657518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
657518	2022-11-10T02:17:35 Z	sentheta	메기 농장 (IOI22_fish)	C++17	37 / 100	1000 ms	98252 KB

fish

#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

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1085 ms	14408 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1085 ms	14408 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

답안 #657518

Compilation message