oj.uz

답안 #596293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596293 2022-07-14T14:46:15 Z Red_Inside 카니발 티켓 (IOI20_tickets) C++17
39 / 100
 3000 ms 2097152 KB 
#include "tickets.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=1e6+10,LOG=17,mod=998244353;
int block = 226, 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>


long long find_maximum(int k, vector <vector <int> > a)
{
	vector <vector <int> > use;
	int n = a.size();
	int m = a[0].size();
	use = a;
	forn(0, i, n-1) forn(0, j, m-1) use[i][j] = -1;
	vector <vector <pii> > b;
	vector <vector <ll> > pref, suff, dp, pred;
	pref.assign(n + 2, {});
	suff.assign(n + 2, {});
	dp.assign(n + 2, {});
	pred.assign(n + 2, {});
	b.assign(n + 2, {});
	int SSS = k * n / 2;
	forn(0, i, n + 1)
	{
		pred[i].assign(SSS + 2, 0);
		dp[i].assign(SSS + 2, -inf);
		b[i].assign(m + 2, mp(0, 0));
		suff[i].assign(m + 2, 0);
		pref[i].assign(m + 2, 0);
	}
	forn(1, i, n)
	{
		forn(1, j, m)
		{
			b[i][j] = {a[i-1][j-1], j};
		}
		sort(b[i].begin() + 1, b[i].begin() + 1 + m);
		reverse(b[i].begin() + 1, b[i].begin() + 1 + m);
	}
	forn(1, i, n)
	{
		forn(1, j, m) pref[i][j] = pref[i][j - 1] + b[i][j].f;
		nfor(1, j, m) suff[i][j] = suff[i][j + 1] + b[i][j].f;
	}
	ll ret = 0;
	dp[0][0] = 0;
	forn(1, i, n)
	{
		int bor = min((i-1) * k, SSS);
		forn(0, j, bor)
		{
			forn(0, take, k)
			{
				if(take + j > SSS) break;
				ll T = dp[i-1][j] + pref[i][take] -suff[i][m-k+take+1];
				if(dp[i][take+j] < T)
				{
					pred[i][take+j] = take;
					dp[i][take+j]=T;
				}
			}
		}
	}
	int cur = SSS;
	set <pii> st;
	forn(0, i, k-1)
	{
		st.insert({0, i});
	}
	ret = dp[n][SSS];
	nfor(1, i, n)
	{
		int take  = pred[i][cur];
		set <pii> nw;
		forn(1, j, take)
		{
			use[i-1][b[i][j].s-1] = st.begin()->s;
			pii temp = *st.begin();
			st.erase(st.begin());
			temp.f++;
			nw.insert(temp);
		}
		forn(m - k + take + 1, j, m)
		{
			use[i-1][b[i][j].s-1] = st.rbegin()->s;
			pii temp = *st.rbegin();
			temp.f--;
			st.erase(*st.rbegin());
			nw.insert(temp);
		}
		st = nw;
		cur -= take;
	}
	allocate_tickets(use);
	return ret;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 16 ms 18772 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 272 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 27 ms 5836 KB Output is correct
6 Correct 539 ms 122276 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 8 ms 2628 KB Output is correct
5 Correct 829 ms 110900 KB Output is correct
6 Runtime error 933 ms 2097152 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 38 ms 4716 KB Output is correct
5 Execution timed out 3102 ms 217376 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 884 KB Output is correct
4 Correct 7 ms 1724 KB Output is correct
5 Correct 11 ms 2676 KB Output is correct
6 Correct 22 ms 3676 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 18 ms 3156 KB Output is correct
10 Correct 17 ms 3256 KB Output is correct
11 Correct 28 ms 4172 KB Output is correct
12 Correct 29 ms 4200 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 884 KB Output is correct
4 Correct 7 ms 1724 KB Output is correct
5 Correct 11 ms 2676 KB Output is correct
6 Correct 22 ms 3676 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 18 ms 3156 KB Output is correct
10 Correct 17 ms 3256 KB Output is correct
11 Correct 28 ms 4172 KB Output is correct
12 Correct 29 ms 4200 KB Output is correct
13 Correct 24 ms 6812 KB Output is correct
14 Correct 37 ms 12480 KB Output is correct
15 Correct 1592 ms 111592 KB Output is correct
16 Execution timed out 3047 ms 217404 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 16 ms 18772 KB Output is correct
7 Correct 1 ms 272 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 27 ms 5836 KB Output is correct
12 Correct 539 ms 122276 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 8 ms 2628 KB Output is correct
17 Correct 829 ms 110900 KB Output is correct
18 Runtime error 933 ms 2097152 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -