oj.uz

Submission #1074872

# Submission time Handle Problem Language Result Execution time Memory
1074872 2024-08-25T15:48:55 Z Dan4Life Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 63800 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
const int mxN = (int)1e5+10;
const int mxN2 = (int)3e2+10;
const ll LINF = (ll)2e18;
int n, m;
struct Fish{ int x, y, w; };
vector<Fish> fishes;
ll dp[mxN][10][10];
ll pref[mxN2][mxN2];
int mxY = 9;

ll max_weights(int N, int M, vi _X, vi _Y, vi _W) {
	n = N, m = M; mxY=min(mxY,N);
	for(int i = 0; i < m; i++) 
		fishes.pb({_X[i]+1,_Y[i]+1,_W[i]});
	sort(all(fishes),[&](Fish a, Fish b){
		if(a.x!=b.x) return a.x<b.x;
		return a.y<b.y;
	});
	for(int i = 0; i < m; i++){
		auto [x,y,w] = fishes[i];
		pref[x][y]+=w;
	}
	for(int i = 0; i <= n; i++)
		for(int j = 1; j <= n; j++)
			pref[i][j]+=pref[i][j-1];
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= mxY; j++)
			for(int k = 0; k <= mxY; k++)
				dp[i][j][k]=-LINF;
	ll ans = 0;
	for(int i = 0; i <= mxY; i++){
		for(int j = 0; j <= mxY; j++){
			if(i>j) dp[2][i][j]=pref[1][i]-pref[1][j];
			else if(i<j) dp[2][i][j]=pref[2][j]-pref[2][i];
			else dp[2][i][j]=0;
			ans=max(ans, dp[2][i][j]+pref[3][i]);
		}
	}
	for(int i = 3; i <= n; i++){
		for(int j = 0; j <= mxY; j++){
			for(int k = 0; k <= mxY; k++){
				ll costi = 0;
				if(k>j) costi=pref[i][k]-pref[i][j];
				for(int l = 0; l <= k; l++){
					ll costi1 = 0;
					if(j>k) costi1 = pref[i-1][j]-pref[i-1][k];
					dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l]+costi1);
				}
				for(int l = k+1; l<= mxY; l++){
					ll costi1 = 0;
					if(j>l) costi1 = pref[i-1][j]-pref[i-1][l];
					dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l]+costi1);
				}
				dp[i][j][k]+=costi;
				ans = max(ans, dp[i][j][k]+pref[i+1][j]);
			}
		}
	}
	return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2656 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2656 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '299', found: '9'
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2656 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Incorrect 1 ms 2652 KB 1st lines differ - on the 1st token, expected: '299', found: '9'
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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