oj.uz

답안 #632562

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632562 2022-08-20T10:42:41 Z Red_Inside 메기 농장 (IOI22_fish) C++17
0 / 100
 1000 ms 34368 KB 
#include "fish.h"
//
#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=5000+100,LOG=20,mod=998244353;
int block = 106, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const ll inf=2e18;
#define y1 yy
#define prev pre
#define pii pair <int, int>

ll n, dp[maxn][maxn][2], dp1[maxn], dp2[maxn], c[maxn];
ll t[4*maxn][3][4], pu[4*maxn][3][4];
vector <pii> vec[maxn];

void push(int v, int tl, int tr, int x, int ty)
{
	if(ty == 3)
	{
		if(pu[v][x][ty] == -1)
		{
			pu[v * 2][x][ty] = -1;
			pu[v * 2 + 1][x][ty] = -1;
			t[v * 2][x][ty] = 0;
			t[v * 2 + 1][x][ty] = 0;
			pu[v][x][ty] = 0;
		}
	}
	else
	{
		if(pu[v][x][ty] == -inf)
		{
			pu[v * 2][x][ty] = -inf;
			pu[v * 2 + 1][x][ty] = -inf;
			t[v * 2][x][ty] = -inf;
			t[v * 2 + 1][x][ty] = -inf;
			pu[v][x][ty] = 0;
		}
	}
}

void upd(int v, int tl, int tr, int pos, ll val, int x, int ty)
{
	if(pos < tl || tr < pos) return;
	if(tl == tr)
	{
		t[v][x][ty] = val;
		return;
	}
	push(v, tl, tr, x, ty);
	upd(v * 2, tl, (tl + tr) / 2, pos, val, x, ty);
	upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val, x, ty);
	if(ty == 3) t[v][x][ty] = t[v * 2][x][ty] + t[v * 2 + 1][x][ty];
	else
		t[v][x][ty] = max(t[v * 2][x][ty], t[v * 2 + 1][x][ty]);
}

ll get(int v, int tl, int tr, int l, int r, int x, int ty)
{
	if(l > tr || r < tl) return (ty == 3 ? 0 : -inf);
	if(l <= tl && tr <= r) return t[v][x][ty];
	push(v, tl, tr, x, ty);
	ll r1 = get(v * 2, tl, (tl + tr) / 2, l, r, x, ty);
	ll r2 = get(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, x, ty);
	if(ty == 3) return r1 + r2;
	return max(r1, r2);
}

ll max_weights(int N, int m, vector <int> x, vector <int> y, vector <int> c)
{
	n = N;
	forn(0, i, m-1)
	{
		vec[x[i]+1].pb({y[i]+1, c[i]});
	}
	set <int> pos;
	forn(1, i, n) pos.insert(i);
	/*for(auto j : vec[1])
	{
		c[j.f]++;
		if(c[j.f] == 1)
			pos.insert(j.f);
	}
	for(auto j : vec[2])
	{
		c[j.f]++;
		if(c[j.f] == 1)
			pos.insert(j.f);
	}*/
	forn(0, i, 2)
	{
		forn(0, j, 2)
		{
			pu[1][i][j] = -inf;
			t[1][i][j] = -inf;
		}
		t[1][i][3] = 0;
		pu[1][i][3] = -1;
	}
	int p = 0;
	for(auto j : vec[1])
	{
		upd(1, 1, n, j.f, j.s, p, 3);
	}
	for(auto j : pos)
	{
		dp[p][j][0] = 0;
	}
	dp1[p] = 0;
	dp2[p] = 0;
	for(auto j : pos)
	{
		upd(1, 1, n, j, max(dp[p][j][0], dp[p][j][1]), p, 1);
		upd(1, 1, n, j, dp[p][j][0] - get(1, 1, n, 1, j, p, 3), p, 0);
	}
	forn(2, i, n)
	{
		p = (p + 1) % 3;
		t[1][p][0] = -inf;
		t[1][p][1] = -inf;
		t[1][p][2] = -inf;
		t[1][p][3] = 0;
		pu[1][p][0] = -inf;
		pu[1][p][1] = -inf;
		pu[1][p][2] = -inf;
		pu[1][p][3] = -1;
		for(auto j : vec[i])
		{
			upd(1, 1, n, j.f, j.s, p, 3);
		}
		/*for(auto j : vec[i + 1])
		{
			c[j.f]++;
			if(c[j.f]==1)
				pos.insert(j.f);
		}
		if(i - 4 >= 1)
		{
			for(auto j : vec[i - 4])
			{
				c[j.f]--;
				if(c[j.f] == 0)
					pos.erase(j.f);
			}
		}*/
		for(auto j : pos)
		{
			upd(1, 1, n, j, max(dp[(p-1+3)%3][j][0],dp[(p-1+3)%3][j][1])+get(1, 1, n, 1, j, p, 3), (p-1+3)%3, 2);
		}
		dp1[p] = 0;
		for(auto j : pos)
		{
			dp[p][j][0] = max(dp2[(p-1+3)%3]+get(1, 1, n, 1, j, (p-1+3)%3, 3),
			get(1, 1, n, 1, j-1, (p-1+3)%3, 0));
			dp[p][j][0] = max(dp[p][j][0], 
			get(1, 1, n, 1, j, (p-2+3)%3, 1)+get(1, 1, n, 1, j, (p-1+3)%3, 3));
			dp[p][j][0] = max(dp[p][j][0],
			get(1, 1, n, j+1, n,(p-2+3)%3, 2));
			dp[p][j][1] = -inf;
			dp[p][j][1] = max(dp[p][j][1], 
			get(1, 1, n, j+1, n, (p-1+3)%3, 2)-get(1, 1, n, 1, j, p, 3));
		}
		dp1[p] = max(dp1[p], get(1, 1, n, 1, n, (p-1+3)%3, 2));
		dp2[p] = max(dp2[(p-1+3)%3], dp1[(p-1+3)%3]);
		for(auto j : pos)
		{
			upd(1, 1, n, j, max(dp[p][j][0], dp[p][j][1]), p, 1);
			upd(1, 1, n, j, dp[p][j][0] - get(1, 1, n, 1, j, p, 3), p, 0);
		}
	}
	ll ans = 0;
	for(auto i : pos)
	{
		ans = max(ans, dp[p][i][0]);
		ans = max(ans, dp[p][i][1]);
	}
	ans = max(ans, dp1[p]);
	ans = max(ans, dp2[p]);
	return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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