oj.uz

답안 #629299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
629299 2022-08-14T10:52:35 Z handlename 메기 농장 (IOI22_fish) C++17
35 / 100
 1000 ms 1799240 KB 
#include <bits/stdc++.h>
//#include "fish.h"
using namespace std;
#define pb push_back
#define mp make_pair

vector<pair<int,long long> > arr[100005];
long long qry(int col,int height){ //prefixsum of col to height
	if (arr[col].empty()) return 0;
	pair<int,long long> lol=mp(height,1e18);
	int pos=upper_bound(arr[col].begin(),arr[col].end(),lol)-arr[col].begin();
	pos--;
	return arr[col][pos].second;
}
vector<long long> dp1[100005]; //col,height,increasing
vector<long long> dp2[100005]; //col,height,decreasing
vector<long long> whack[100005];
long long max_weights(int n,int m,vector<int> x,vector<int> y,vector<int> w){
	for (int i=0;i<m;i++){
		x[i]++;
		y[i]++;
		arr[x[i]].pb(mp(y[i],w[i]));
	}
	for (int i=1;i<=n;i++){
		arr[i].pb(mp(0,0));
		sort(arr[i].begin(),arr[i].end());
		for (int j=1;j<(int)arr[i].size();j++){
			arr[i][j].second+=arr[i][j-1].second;
		}
	}
	for (int j=0;j<=n;j++){
		dp1[0].pb(0);
		dp2[0].pb(0);
		whack[0].pb(j);
	}
	for (int i=1;i<=n;i++){
		for (int j=0;j<=n;j++){
			dp1[i].pb(-1e18);
			dp2[i].pb(-1e18);
			whack[i].pb(j);
		}
	}
	for (int i=1;i<=n;i++){ //col
		long long maxi=0;
		for (int j=0;j<=n;j++){
			maxi=max(maxi,dp1[i-1][j]-qry(i,j)-qry(i-1,j));
			if (i>=2){
				maxi=max(maxi,dp2[i-2][j]-qry(i-1,j));
			}
			dp1[i][j]=maxi+qry(i-1,j)+qry(i+1,j);
		}
		maxi=0;
		if (i>=2){
			for (int j=n;j>=0;j--){
				maxi=max(maxi,dp2[i-2][j]);
				dp1[i][j]=max(dp1[i][j],maxi+qry(i+1,j));
			}
		}
		maxi=0;
		for (int j=n;j>=0;j--){
			maxi=max(maxi,dp2[i-1][j]);
			dp2[i][j]=maxi+qry(i+1,j)-qry(i,j);
		}
		for (int j=0;j<=n;j++){
			dp2[i][j]=max(dp2[i][j],dp1[i][j]);
		}
	}
	long long ans=0;
	for (int j=0;j<=n;j++){
		ans=max(ans,dp2[n][j]);
	}
	return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1095 ms 1621592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9588 KB Output is correct
4 Correct 7 ms 9664 KB Output is correct
5 Correct 5 ms 9644 KB Output is correct
6 Correct 5 ms 9696 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 7 ms 10580 KB Output is correct
10 Correct 13 ms 13524 KB Output is correct
11 Correct 8 ms 10600 KB Output is correct
12 Correct 12 ms 13396 KB Output is correct
13 Correct 7 ms 9940 KB Output is correct
14 Correct 12 ms 13396 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9588 KB Output is correct
4 Correct 7 ms 9664 KB Output is correct
5 Correct 5 ms 9644 KB Output is correct
6 Correct 5 ms 9696 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 7 ms 10580 KB Output is correct
10 Correct 13 ms 13524 KB Output is correct
11 Correct 8 ms 10600 KB Output is correct
12 Correct 12 ms 13396 KB Output is correct
13 Correct 7 ms 9940 KB Output is correct
14 Correct 12 ms 13396 KB Output is correct
15 Correct 12 ms 13352 KB Output is correct
16 Correct 7 ms 10068 KB Output is correct
17 Correct 41 ms 15548 KB Output is correct
18 Correct 42 ms 15948 KB Output is correct
19 Correct 32 ms 16036 KB Output is correct
20 Correct 32 ms 15984 KB Output is correct
21 Correct 34 ms 15984 KB Output is correct
22 Correct 52 ms 18124 KB Output is correct
23 Correct 22 ms 13912 KB Output is correct
24 Correct 41 ms 14936 KB Output is correct
25 Correct 14 ms 13396 KB Output is correct
26 Correct 18 ms 13800 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9588 KB Output is correct
4 Correct 7 ms 9664 KB Output is correct
5 Correct 5 ms 9644 KB Output is correct
6 Correct 5 ms 9696 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 7 ms 10580 KB Output is correct
10 Correct 13 ms 13524 KB Output is correct
11 Correct 8 ms 10600 KB Output is correct
12 Correct 12 ms 13396 KB Output is correct
13 Correct 7 ms 9940 KB Output is correct
14 Correct 12 ms 13396 KB Output is correct
15 Correct 12 ms 13352 KB Output is correct
16 Correct 7 ms 10068 KB Output is correct
17 Correct 41 ms 15548 KB Output is correct
18 Correct 42 ms 15948 KB Output is correct
19 Correct 32 ms 16036 KB Output is correct
20 Correct 32 ms 15984 KB Output is correct
21 Correct 34 ms 15984 KB Output is correct
22 Correct 52 ms 18124 KB Output is correct
23 Correct 22 ms 13912 KB Output is correct
24 Correct 41 ms 14936 KB Output is correct
25 Correct 14 ms 13396 KB Output is correct
26 Correct 18 ms 13800 KB Output is correct
27 Correct 421 ms 257812 KB Output is correct
28 Correct 185 ms 38448 KB Output is correct
29 Correct 591 ms 271536 KB Output is correct
30 Execution timed out 1022 ms 278340 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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