oj.uz

Submission #428439

# Submission time Handle Problem Language Result Execution time Memory
428439 2021-06-15T11:50:52 Z MarcoMeijer Carnival Tickets (IOI20_tickets) C++14
39 / 100
 3000 ms 2097156 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }

const ll INF = 1e18;

ll find_maximum(int k, vector<vi> x) {
	int n = x.size(); // colors
	int m = x[0].size(); // tickets per color
    int N = n*k/2;

    vector<vi> y = x;
    RE(i,n) sort(all(y[i]));

    vector<vll> dp ; // dp [i][j] = maximum sum with the first i colors, and a total of j negative tickets
    vector<vi > pre; // pre[i][j] = how many negative tickets of color i you should pick to get dp[i][j]
    dp .assign(n,vll(N+1,-INF));
    pre.assign(n,vi (N+1,0));
    RE(i,n) {
        ll tot = 0;
        RE(l,k) tot += y[i][m-1-l];
        int x = m-k;
        RE(l,k+1) {
            // take l negative tickets
            REP(j,l,N+1) {
                ll nRes = (i ? dp[i-1][j-l] : (j == l ? 0ll : -INF)) + tot;
                if(nRes > dp[i][j]) {
                    dp [i][j] = nRes;
                    pre[i][j] = l;
                }
            }

            if(l == k) continue;
            tot -= y[i][l];
            tot -= y[i][x++];
        }
    }

    // reconstruct the answer
	vector<vi> answer(n,vi(m,-1));
    vector<vi> sx(n,vi());
    RE(i,n) RE(j,m) sx[i].pb(j);
    RE(i,n) {
        sort(all(sx[i]),[&](int a, int b) {
            return x[i][a] < x[i][b];
        });
    }
    vi nextNeg, nextPos;
    RE(i,n/2) RE(j,k) nextNeg.pb(j);
    int curNeg = N;
    REV(i,0,n) {
        int len = pre[i][curNeg];
        vi used; used.assign(k,0);
        RE(j,len)
            answer[i][sx[i][j]] = nextNeg.back(), used[nextNeg.back()] = 1, nextNeg.pop_back();
        RE(j,k)
            if(!used[j])
                nextPos.pb(j);
        REP(j,m-k+len,m)
            answer[i][sx[i][j]] = nextPos.back(), nextPos.pop_back();
        curNeg -= len;
    }
	allocate_tickets(answer);

	return dp[n-1][N];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 14 ms 14128 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 38 ms 3812 KB Output is correct
6 Correct 880 ms 85608 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 17 ms 2020 KB Output is correct
5 Correct 1927 ms 82460 KB Output is correct
6 Runtime error 1945 ms 2097156 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 58 ms 3580 KB Output is correct
5 Execution timed out 3051 ms 161032 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 7 ms 1228 KB Output is correct
5 Correct 18 ms 1996 KB Output is correct
6 Correct 31 ms 2832 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 20 ms 2420 KB Output is correct
10 Correct 19 ms 2452 KB Output is correct
11 Correct 36 ms 3168 KB Output is correct
12 Correct 36 ms 3208 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 7 ms 1228 KB Output is correct
5 Correct 18 ms 1996 KB Output is correct
6 Correct 31 ms 2832 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 20 ms 2420 KB Output is correct
10 Correct 19 ms 2452 KB Output is correct
11 Correct 36 ms 3168 KB Output is correct
12 Correct 36 ms 3208 KB Output is correct
13 Correct 30 ms 5188 KB Output is correct
14 Correct 44 ms 9496 KB Output is correct
15 Correct 2154 ms 83336 KB Output is correct
16 Execution timed out 3076 ms 160964 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 14 ms 14128 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 38 ms 3812 KB Output is correct
12 Correct 880 ms 85608 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 17 ms 2020 KB Output is correct
17 Correct 1927 ms 82460 KB Output is correct
18 Runtime error 1945 ms 2097156 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -