Submission #556907

#	Time	Username	Problem	Language	Result	Execution time	Memory
556907		topovik	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	868 ms	70824 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>

//#ifdef _WIN32
//# define I64 "%I64d"
//#else
//# define I64 "%lld"
//#endif

typedef long long ll;

using namespace std;
//
//static int n;
//static int m;
//static int k;
//static std::vector<std::vector<int> > d;
//static std::vector<std::vector<int> > x;
//static int called = 0;
//
//long long find_maximum(int , std::vector<std::vector<int> > ) ;
//
//
//static void _assert (bool cond, const char* error) {
//    if (!cond) {
//        printf("%s\n", error);
//        exit(0);
//    }
//}
//
//void allocate_tickets (std::vector<std::vector<int> > _d) {
//    _assert(!called, "allocate_tickets called more than once");
//    d = _d;
//    _assert((int) d.size() == n, "allocate_tickets called with parameter of wrong size");
//    for (int i = 0;  i < n;  i++)
//        _assert((int) d[i].size() == m, "allocate_tickets called with parameter of wrong size");
//    called = 1;
//}
//
//int main () {
//    assert(scanf("%d %d %d", &n, &m, &k) == 3);
//    x.resize(n);
//    for (int i = 0;  i < n;  i++) {
//        x[i].resize(m);
//        for (int j=0;  j < m;  j++)
//            assert(scanf("%d", &x[i][j]) == 1);
//    }
//    fclose(stdin);
//
//    long long answer = find_maximum(k, x);
//    _assert(called, "failure to call allocate_tickets");
//    printf(I64 "\n", answer);
//    for (int i = 0;  i < n;  i++) {
//        for (int j = 0;  j < m;  j++) {
//            if (j)
//                printf(" ");
//            printf("%d", d[i][j]);
//        }
//        printf("\n");
//    }
//}



const int N = 3e3;
const int M = 1500;
const ll oo = 1e18;

ll dp[N][N];
int pred[N][N];
int a[N][N];
int n1, m1;


ll Check(ll x)
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) dp[i][j] = -oo;
    dp[0][M] = 0;
    for (int i = 1; i <= n1; i++)
    {
        for (int j : {a[i - 1][0], a[i - 1][m1 - 1]})
            for (int cur = 0; cur < N; cur++)
            {
                if (j >= x && cur > 0)
                {
                    if (dp[i - 1][cur - 1] + abs(j - x) > dp[i][cur])
                    {
                        dp[i][cur] = dp[i - 1][cur - 1] + abs(j - x);
                        pred[i][cur] = cur - 1;
                    }
                }
                if (j <= x && cur < N - 1)
                {
                    if (dp[i - 1][cur + 1] + abs(j - x) > dp[i][cur])
                    {
                        dp[i][cur] = dp[i - 1][cur + 1] + abs(j - x);
                        pred[i][cur] = cur + 1;
                    }
                }
            }
    }
    return dp[n1][M];
}

long long find_maximum(int k, std::vector<std::vector<int> > x) {
	n1 = x.size();
	m1 = x[0].size();
    std::vector<std::vector<int> > ans;
    ans.resize(n1);
    for (int i = 0; i < n1; i++) ans[i].resize(m1);
    if (m1 == 1)
    {

        for (int i = 0; i < n1; i++)
        {
            if (i < n1 / 2)
            {
                for (int j = 0; j < m1; j++)
                    if (j < k) ans[i][j] = j;
                    else ans[i][j] = -1;
            }
            else
            {
                for (int j = m1 - 1; j >= 0; j--)
                    if (j >= (m1 - k)) ans[i][j] = m1 - j - 1;
                    else ans[i][j] = -1;
            }
        }
        int a[k][n1];
        for (int i = 0; i < n1; i++)
            for (int j = 0; j < m1; j++)
                if (ans[i][j] != -1) a[ans[i][j]][i] = x[i][j];
        ll sum = 0;
        for (int i = 0; i < k; i++)
        {
            sort(a[i], a[i] + n1);
            for (int j = 0; j < n1; j++) sum += abs(a[i][j] - a[i][n1 / 2]);
        }
        allocate_tickets(ans);
        return sum;
    }
    else
    {
        for (int i = 0; i < n1; i++)
            for (int j = 0; j < m1; j++) ans[i][j] = -1, a[i][j] = x[i][j];
        ll l = 0, r = 1e9;
        while (r - l > 5)
        {
            int l1 = (r - l) / 3;
            if (Check(l + l1) > Check(r - l1)) l += l1;
            else r -= l1;
        }
        ll ns = Check(l);
        ll l1 = l;
        for (int i = l; i <= r; i++)
        {
            ll c = Check(i);
            if (c > ns)
            {
                ns = c;
                l1 = i;
            }
        }
        Check(l1);
        int cur = M;
        for (int i = n1; i > 0; i--)
        {
            if (pred[i][cur] < cur) ans[i - 1][m1 - 1] = 0;
            else                    ans[i - 1][0] = 0;
            cur = pred[i][cur];
        }
        allocate_tickets(ans);
        return ns;
    }
}
/*
2 3 2
0 2 5
1 1 3

4 2 1
5 9
1 4
3 6
2 7
*/

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10