oj.uz

Submission #428508

# Submission time Handle Problem Language Result Execution time Memory
428508 2021-06-15T12:25:03 Z alishahali1382 Carnival Tickets (IOI20_tickets) C++14
39 / 100
 3000 ms 1008788 KB 
#include "tickets.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": "; for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())

const int inf=1000000100; // 1e9
const ll INF=10000000001000000; // 1e16
const int mod=1000000007;
const int MAXN=1510, LOG=20;

int n, m, k, x, y, u, v, t, a, b, ans;
int A[MAXN][MAXN];
ll B[MAXN][MAXN];
ll dp[MAXN][3300];
int par[MAXN][3300];
vector<vi> out;
vi out1[MAXN], out2[MAXN];

inline bool upd(ll &x, ll y){
	if (x>=y) return 0;
	x=y;
	return 1;
}

ll find_maximum(int _k, vector<vi> _A) {
	n=SZ(_A);
	m=SZ(_A[0]);
	k=_k;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++) A[i][j]=_A[i-1][j-1];
		for (int j=1; j<=k; j++) B[i][0]-=A[i][j];
		for (int j=1; j<=k; j++) B[i][j]=B[i][j-1]+A[i][m-j+1]+A[i][k-j+1];
		// B convex increasing
		// B[j]<=B[j+1]
		// B[j]-B[j-1]>=B[j+1]-B[j]
	}
	out.resize(n, vector<int>(m, -1));
	// assert(k==1);
	memset(dp, -63, sizeof(dp));
	dp[0][0]=0;
	for (int i=1; i<=n; i++){
		for (int j=0; j<=i*k && j<=n*k/2; j++){
			for (int t=0; t<=min(k, j); t++){
				if (upd(dp[i][j], dp[i-1][j-t]+B[i][t])) par[i][j]=t;
			}
		}
	}
	ll res=dp[n][n*k/2];
	debug(res)
	int j=n*k/2;
	for (int i=n; i; i--){
		for (int x=1; x<=k-par[i][j]; x++) out1[i].pb(x);
		for (int x=0; x<par[i][j]; x++) out2[i].pb(m-x);
		j-=par[i][j];
	}
	assert(!j);

	while (k--){
		vector<pii> vec;
		for (int i=1; i<=n; i++) vec.pb({SZ(out1[i]), i});
		sort(all(vec));
		for (int ii=1; ii<=n; ii++){
			int i=vec[ii-1].second;
			if (ii>n/2){
				assert(SZ(out1[i]));
				out[i-1][out1[i].back()-1]=k;
				out1[i].pop_back();
			}
			else{
				assert(SZ(out2[i]));
				out[i-1][out2[i].back()-1]=k;
				out2[i].pop_back();
			}
		}
	}
	allocate_tickets(out);
	return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39372 KB Output is correct
2 Correct 20 ms 39464 KB Output is correct
3 Correct 19 ms 39488 KB Output is correct
4 Correct 20 ms 40348 KB Output is correct
5 Correct 25 ms 43224 KB Output is correct
6 Correct 33 ms 61140 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39344 KB Output is correct
2 Correct 20 ms 39372 KB Output is correct
3 Correct 22 ms 39492 KB Output is correct
4 Correct 23 ms 40524 KB Output is correct
5 Correct 48 ms 45496 KB Output is correct
6 Correct 690 ms 114760 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39388 KB Output is correct
2 Correct 21 ms 39396 KB Output is correct
3 Correct 19 ms 39416 KB Output is correct
4 Correct 26 ms 40900 KB Output is correct
5 Runtime error 2493 ms 1008788 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39372 KB Output is correct
2 Correct 19 ms 39372 KB Output is correct
3 Correct 18 ms 39448 KB Output is correct
4 Correct 42 ms 41164 KB Output is correct
5 Execution timed out 3067 ms 47584 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39368 KB Output is correct
2 Correct 20 ms 40544 KB Output is correct
3 Correct 21 ms 40572 KB Output is correct
4 Correct 22 ms 40652 KB Output is correct
5 Correct 27 ms 40920 KB Output is correct
6 Correct 36 ms 41164 KB Output is correct
7 Correct 22 ms 39500 KB Output is correct
8 Correct 19 ms 40384 KB Output is correct
9 Correct 30 ms 40968 KB Output is correct
10 Correct 41 ms 41012 KB Output is correct
11 Correct 41 ms 41104 KB Output is correct
12 Correct 75 ms 41124 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39368 KB Output is correct
2 Correct 20 ms 40544 KB Output is correct
3 Correct 21 ms 40572 KB Output is correct
4 Correct 22 ms 40652 KB Output is correct
5 Correct 27 ms 40920 KB Output is correct
6 Correct 36 ms 41164 KB Output is correct
7 Correct 22 ms 39500 KB Output is correct
8 Correct 19 ms 40384 KB Output is correct
9 Correct 30 ms 40968 KB Output is correct
10 Correct 41 ms 41012 KB Output is correct
11 Correct 41 ms 41104 KB Output is correct
12 Correct 75 ms 41124 KB Output is correct
13 Correct 57 ms 45680 KB Output is correct
14 Correct 51 ms 46692 KB Output is correct
15 Runtime error 2696 ms 988668 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39372 KB Output is correct
2 Correct 20 ms 39464 KB Output is correct
3 Correct 19 ms 39488 KB Output is correct
4 Correct 20 ms 40348 KB Output is correct
5 Correct 25 ms 43224 KB Output is correct
6 Correct 33 ms 61140 KB Output is correct
7 Correct 18 ms 39344 KB Output is correct
8 Correct 20 ms 39372 KB Output is correct
9 Correct 22 ms 39492 KB Output is correct
10 Correct 23 ms 40524 KB Output is correct
11 Correct 48 ms 45496 KB Output is correct
12 Correct 690 ms 114760 KB Output is correct
13 Correct 19 ms 39388 KB Output is correct
14 Correct 21 ms 39396 KB Output is correct
15 Correct 19 ms 39416 KB Output is correct
16 Correct 26 ms 40900 KB Output is correct
17 Runtime error 2493 ms 1008788 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -