oj.uz

Submission #428503

# Submission time Handle Problem Language Result Execution time Memory
428503 2021-06-15T12:23:20 Z alishahali1382 Carnival Tickets (IOI20_tickets) C++14
39 / 100
 3000 ms 573296 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];
	}
	if (j) goto Hell;

	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();
			}
		}
	}
	Hell:
	allocate_tickets(out);
	return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39372 KB Output is correct
2 Correct 21 ms 39472 KB Output is correct
3 Correct 21 ms 39424 KB Output is correct
4 Correct 21 ms 40320 KB Output is correct
5 Correct 21 ms 43208 KB Output is correct
6 Correct 36 ms 61204 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39324 KB Output is correct
2 Correct 21 ms 39356 KB Output is correct
3 Correct 25 ms 39524 KB Output is correct
4 Correct 30 ms 40576 KB Output is correct
5 Correct 57 ms 46192 KB Output is correct
6 Correct 684 ms 115400 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39388 KB Output is correct
2 Correct 22 ms 39372 KB Output is correct
3 Correct 23 ms 39500 KB Output is correct
4 Correct 30 ms 40944 KB Output is correct
5 Incorrect 1770 ms 573296 KB There is no ticket of color 0 on day 0
6 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39372 KB Output is correct
2 Correct 24 ms 39372 KB Output is correct
3 Correct 23 ms 39436 KB Output is correct
4 Correct 49 ms 41128 KB Output is correct
5 Execution timed out 3092 ms 47608 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39404 KB Output is correct
2 Correct 26 ms 40524 KB Output is correct
3 Correct 28 ms 40508 KB Output is correct
4 Correct 27 ms 40688 KB Output is correct
5 Correct 30 ms 40936 KB Output is correct
6 Correct 38 ms 41072 KB Output is correct
7 Correct 22 ms 39492 KB Output is correct
8 Correct 23 ms 40464 KB Output is correct
9 Correct 34 ms 40948 KB Output is correct
10 Correct 38 ms 40972 KB Output is correct
11 Correct 48 ms 41124 KB Output is correct
12 Correct 44 ms 41164 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39404 KB Output is correct
2 Correct 26 ms 40524 KB Output is correct
3 Correct 28 ms 40508 KB Output is correct
4 Correct 27 ms 40688 KB Output is correct
5 Correct 30 ms 40936 KB Output is correct
6 Correct 38 ms 41072 KB Output is correct
7 Correct 22 ms 39492 KB Output is correct
8 Correct 23 ms 40464 KB Output is correct
9 Correct 34 ms 40948 KB Output is correct
10 Correct 38 ms 40972 KB Output is correct
11 Correct 48 ms 41124 KB Output is correct
12 Correct 44 ms 41164 KB Output is correct
13 Correct 52 ms 45636 KB Output is correct
14 Correct 55 ms 46712 KB Output is correct
15 Incorrect 1805 ms 573212 KB There is no ticket of color 0 on day 0
16 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39372 KB Output is correct
2 Correct 21 ms 39472 KB Output is correct
3 Correct 21 ms 39424 KB Output is correct
4 Correct 21 ms 40320 KB Output is correct
5 Correct 21 ms 43208 KB Output is correct
6 Correct 36 ms 61204 KB Output is correct
7 Correct 20 ms 39324 KB Output is correct
8 Correct 21 ms 39356 KB Output is correct
9 Correct 25 ms 39524 KB Output is correct
10 Correct 30 ms 40576 KB Output is correct
11 Correct 57 ms 46192 KB Output is correct
12 Correct 684 ms 115400 KB Output is correct
13 Correct 27 ms 39388 KB Output is correct
14 Correct 22 ms 39372 KB Output is correct
15 Correct 23 ms 39500 KB Output is correct
16 Correct 30 ms 40944 KB Output is correct
17 Incorrect 1770 ms 573296 KB There is no ticket of color 0 on day 0
18 Halted 0 ms 0 KB -