oj.uz

Submission #627098

# Submission time Handle Problem Language Result Execution time Memory
627098 2022-08-12T07:32:30 Z movl228 Catfish Farm (IOI22_fish) C++17
17 / 100
 84 ms 7272 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

long long max_weights(int n,int m,vector <int> x,vector <int> y,vector <int> w){
	bool sub1=1;
	for (int i:x){
		if (i%2==1) sub1=0;
	}
	if (sub1){
		return accumulate(w.begin(),w.end(),0ll);
	}
	if (*max_element(x.begin(),x.end())<=-1){
		long long mx[2]={0,0};
		for (int i=0; i<m; i++) mx[x[i]]+=w[i];
		return max(mx[0],mx[1]);
	}
	if (n<=300&&*max_element(y.begin(),y.end())<=8){
		long long a[n+1][n+1],s[n+1][n+1];
		for (int i=0; i<=n; i++){
			for (int j=0; j<=n; j++) a[i][j]=s[i][j]=0;
		}
		for (int i=0; i<m; i++) a[y[i]+1][x[i]+1]=w[i];
		for (int col=0; col<=n; col++){
			for (int i=1; i<=n; i++) s[col][i]=s[col][i-1]+a[i][col];
		}
		int l=min(8,n);
		long long dp[n+1][l+1][l+1];
		for (int i=0; i<=n; i++){
			for (int j=0; j<=l; j++){
				for (int k=0; k<=l; k++) dp[i][j][k]=-1e18;
			}
		}
		dp[0][0][0]=0;
		for (int i=0; i<n; i++){
			for (int j=0; j<=l; j++){
				for (int k=0; k<=l; k++){
					for (int nxt=0; nxt<=l; nxt++){
						dp[i+1][k][nxt]=max(dp[i+1][k][nxt],dp[i][j][k]+(nxt>max(j,k)?s[i][nxt]-s[i][max(j,k)]:0ll)-s[i+1][min(k,nxt)]+(i+2<=n?s[i+2][nxt]:0ll));
					}
				}
			}
		}
		long long ans=0;
		for (int i=0; i<=n; i++){
			for (int j=0; j<=l; j++){
				for (int k=0; k<=l; k++){
					ans=max(ans,dp[i][j][k]);
				}
			}
		}
		return ans;
	}
	return 0ll;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2124 KB Output is correct
2 Correct 29 ms 2612 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 84 ms 7272 KB Output is correct
6 Correct 83 ms 7264 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 1876 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2124 KB Output is correct
2 Correct 29 ms 2612 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 84 ms 7272 KB Output is correct
6 Correct 83 ms 7264 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 48 ms 3992 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
9 Halted 0 ms 0 KB -