oj.uz

Submission #300621

# Submission time Handle Problem Language Result Execution time Memory
300621 2020-09-17T10:31:53 Z MarcoMeijer Carnival Tickets (IOI20_tickets) C++14
0 / 100
 2 ms 416 KB 
#include <bits/stdc++.h>
#include "tickets.h"

using namespace std;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<ii> vii;

const int INF=1e9;
const int MX=1505;

int n, k, m;
vvi X;
vvi answer;
vvll dp;
vvll dpOpt;
ll cost[MX][MX];
int big[MX];
int ticketBig[MX], ticketSmall[MX];

void searchDp(int x, int y) {
    if(x == 0) return;
    int opt = dpOpt[x][y];
    big[x-1] = opt;
    searchDp(x-1, y-opt);
}

ll find_maximum(int _k, vvi _x) {
    k = _k; X = _x;
    n = X.size();
    m = X[0].size();
    int totBig = (n/2)*k;

    // fill cost
    RE(i,n) {
        int sm = 0;
        RE(j,k) sm -= X[i][j];
        RE(j,k+1) {
            cost[i][j] = sm;
            if(j == k) break;
            sm += X[i][k-1-j];
            sm += X[i][m-1-j];
        }
    }

    // fill dp
    dp.assign(n+1,vll(totBig+1, -1e18));
    dpOpt.assign(n+1,vll(totBig+1, -1));
    dp[0][0] = 0;
    REP(i,1,n) RE(j,totBig+1) {
        RE(I,min(k+1,j+1)) {
            ll ndp = dp[i-1][j-I] + cost[i-1][I];
            if(ndp > dp[i][j]) {
                dp[i][j] = ndp;
                dpOpt[i][j] = I;
            }
        }
    }
    searchDp(n,totBig);

    // create answer
    ll ans = 0;
    answer.assign(n,vi(m,-1));
    RE(i,n) ticketBig[i]=m-1, ticketSmall[i]=0;
    RE(i,k) {
        vii best;
        RE(i,n) best.pb({big[i], i});
        sort(all(best), greater<ii>());
        RE(j,n/2) {
            int x = best[j].se;
            ans += X[x][ticketBig[x]];
            big[ticketBig[x]]--;
            answer[x][ticketBig[x]--] = i;
        }
        RE(j,n/2) {
            int x = best[j+n/2].se;
            ans -= X[x][ticketSmall[x]];
            answer[x][ticketSmall[x]++] = i;
        }
    }

    allocate_tickets(answer);
    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 298620960 but the tickets gives a total value of -298620960
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Contestant returned 234650292 but the tickets gives a total value of -234650292
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 416 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 11 but the tickets gives a total value of -1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 11 but the tickets gives a total value of -1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 11 but the tickets gives a total value of -1
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 298620960 but the tickets gives a total value of -298620960
2 Halted 0 ms 0 KB -