답안 #630655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
630655	2022-08-16T20:24:30 Z	CSQ31	메기 농장 (IOI22_fish)	C++17	9 / 100	423 ms	87400 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define sz(a) (int)(a.size())
//0 -> previous is lower
//1 -> previous is higher
const int MAXN = 111111;
vector<int>st[MAXN];
vector<pii>fish[MAXN];
vector<ll>dp[2][MAXN],pre[3][MAXN];
int cnt[MAXN];
const ll INF = -1e17;
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]++;
		fish[X[i]].push_back({Y[i],i});
	}
	for(int i=0;i<=n;i++){
		vector<pii>f;
		st[i].push_back(0);
		if(i){
			for(auto x:fish[i-1]){
				st[i].push_back(x.fi);
				f.push_back(x);
			}
		}
		for(auto x:fish[i]){
			st[i].push_back(x.fi);
			f.push_back(x);
		}
		for(auto x:fish[i+1]){
			st[i].push_back(x.fi);
			f.push_back(x);
		}
		sort(st[i].begin(),st[i].end());
		sort(f.begin(),f.end());
		st[i].resize(unique(st[i].begin(),st[i].end()) - st[i].begin());
		cnt[i] = st[i].size();
		for(int k=0;k<3;k++)pre[k][i].assign(cnt[i],0);
		for(int k=0;k<2;k++)dp[k][i].assign(cnt[i],INF);
		int ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1 < sz(f) && f[ptr+1].fi <= st[i][j]){
				ptr++;
				int id = f[ptr].se;
				if(Y[id] != st[i][j])continue;
				if(X[id] == i-1)pre[0][i][j]+=W[id];
				if(X[id] == i  )pre[1][i][j]+=W[id];
				if(X[id] == i+1)pre[2][i][j]+=W[id];
			}
		}
		for(int k=0;k<3;k++){
			for(int j=1;j<cnt[i];j++)pre[k][i][j]+=pre[k][i][j-1];
		}
	}
	dp[0][0][0] = 0;
	for(int i=1;i<=n;i++){
		ll mx = INF;
		int ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1<cnt[i-1] && st[i-1][ptr+1] <= st[i][j]){
				ptr++;
				mx = max(mx,dp[0][i-1][ptr] - pre[1][i-1][j]);
			}
			dp[0][i][j] = max(dp[0][i][j],mx + pre[0][i][j]);
		}
		mx = INF;
		ptr = cnt[i-1];
		for(int j=cnt[i]-1;j>=0;j--){
			while(ptr-1>=0 && st[i-1][ptr-1] >= st[i][j]){
				ptr--;
				mx = max(mx,dp[0][i-1][ptr] + pre[1][i][j]);
				mx = max(mx,dp[1][i-1][ptr] + pre[1][i][j]);
			}
			dp[1][i][j] = max(dp[1][i][j],mx - pre[1][i][j]);	
		}
		if(i<2)continue;
		mx = INF;
		ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1 < cnt[i-2] && st[i-2][ptr+1] <= st[i][j]){
				ptr++;
				mx = max(mx,dp[0][i-2][ptr]);
				mx = max(mx,dp[1][i-2][ptr]);
			}
			dp[0][i][j] = max(dp[0][i][j],mx + pre[0][i][j]);
		}
	}
  ll ans = 0;
  for(ll x:dp[0][n])ans = max(ans,x);
  for(ll x:dp[1][n])ans = max(ans,x);
  return ans;
}

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	118 ms	49312 KB	Output is correct
2	Correct	134 ms	54228 KB	Output is correct
3	Correct	45 ms	37736 KB	Output is correct
4	Correct	45 ms	37680 KB	Output is correct
5	Correct	312 ms	87400 KB	Output is correct
6	Incorrect	423 ms	81796 KB	1st lines differ - on the 1st token, expected: '300000000000000', found: '700299996000000000'
7	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	18552 KB	Output is correct
2	Incorrect	204 ms	56728 KB	1st lines differ - on the 1st token, expected: '40604614618209', found: '44152097264951'
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	37740 KB	Output is correct
2	Correct	45 ms	37836 KB	Output is correct
3	Correct	79 ms	38716 KB	Output is correct
4	Correct	69 ms	39620 KB	Output is correct
5	Correct	114 ms	43204 KB	Output is correct
6	Correct	108 ms	43272 KB	Output is correct
7	Correct	109 ms	43212 KB	Output is correct
8	Correct	115 ms	43216 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	18516 KB	Output is correct
2	Correct	10 ms	18584 KB	Output is correct
3	Correct	9 ms	18516 KB	Output is correct
4	Correct	9 ms	18516 KB	Output is correct
5	Correct	9 ms	18516 KB	Output is correct
6	Correct	9 ms	18572 KB	Output is correct
7	Correct	9 ms	18516 KB	Output is correct
8	Correct	10 ms	18520 KB	Output is correct
9	Correct	10 ms	18644 KB	Output is correct
10	Correct	10 ms	18772 KB	Output is correct
11	Incorrect	10 ms	18644 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '280895000843'
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	18516 KB	Output is correct
2	Correct	10 ms	18584 KB	Output is correct
3	Correct	9 ms	18516 KB	Output is correct
4	Correct	9 ms	18516 KB	Output is correct
5	Correct	9 ms	18516 KB	Output is correct
6	Correct	9 ms	18572 KB	Output is correct
7	Correct	9 ms	18516 KB	Output is correct
8	Correct	10 ms	18520 KB	Output is correct
9	Correct	10 ms	18644 KB	Output is correct
10	Correct	10 ms	18772 KB	Output is correct
11	Incorrect	10 ms	18644 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '280895000843'
12	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	18516 KB	Output is correct
2	Correct	10 ms	18584 KB	Output is correct
3	Correct	9 ms	18516 KB	Output is correct
4	Correct	9 ms	18516 KB	Output is correct
5	Correct	9 ms	18516 KB	Output is correct
6	Correct	9 ms	18572 KB	Output is correct
7	Correct	9 ms	18516 KB	Output is correct
8	Correct	10 ms	18520 KB	Output is correct
9	Correct	10 ms	18644 KB	Output is correct
10	Correct	10 ms	18772 KB	Output is correct
11	Incorrect	10 ms	18644 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '280895000843'
12	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	37740 KB	Output is correct
2	Correct	45 ms	37836 KB	Output is correct
3	Correct	79 ms	38716 KB	Output is correct
4	Correct	69 ms	39620 KB	Output is correct
5	Correct	114 ms	43204 KB	Output is correct
6	Correct	108 ms	43272 KB	Output is correct
7	Correct	109 ms	43212 KB	Output is correct
8	Correct	115 ms	43216 KB	Output is correct
9	Correct	130 ms	51036 KB	Output is correct
10	Correct	86 ms	33716 KB	Output is correct
11	Correct	176 ms	48220 KB	Output is correct
12	Correct	11 ms	18516 KB	Output is correct
13	Correct	13 ms	18532 KB	Output is correct
14	Correct	10 ms	18516 KB	Output is correct
15	Correct	10 ms	18552 KB	Output is correct
16	Correct	10 ms	18516 KB	Output is correct
17	Correct	10 ms	18516 KB	Output is correct
18	Correct	45 ms	37648 KB	Output is correct
19	Correct	47 ms	37740 KB	Output is correct
20	Correct	42 ms	37740 KB	Output is correct
21	Correct	45 ms	37740 KB	Output is correct
22	Incorrect	162 ms	48872 KB	1st lines differ - on the 1st token, expected: '45561826463480', found: '45403677411158'
23	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	118 ms	49312 KB	Output is correct
2	Correct	134 ms	54228 KB	Output is correct
3	Correct	45 ms	37736 KB	Output is correct
4	Correct	45 ms	37680 KB	Output is correct
5	Correct	312 ms	87400 KB	Output is correct
6	Incorrect	423 ms	81796 KB	1st lines differ - on the 1st token, expected: '300000000000000', found: '700299996000000000'
7	Halted	0 ms	0 KB	-

답안 #630655

Compilation message