Submission #307473

#	Time	Username	Problem	Language	Result	Execution time	Memory
307473		nicolaalexandra	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	3073 ms	76920 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
#define DIM 2000
#define INF 2000000000000000000LL
using namespace std;

int n,m;
long long dp[DIM][DIM];
int t[DIM][DIM];
pair <int,int> poz[DIM];

long long find_maximum (int k, vector<vector<int> > x){
    n = x.size(), m = x[0].size();
    int i,j;
    vector <pair<int,int> > v;
    vector <vector<int> > ans;
    ans.resize(n);
    for (i=0;i<n;i++)
        ans[i].resize(m,-1);

    for (i=0;i<n;i++)
        poz[i].first = 0, poz[i].second = m-1;

    long long sum = 0;
    for (int pas=0;pas<k;pas++){

        /// dp[i][j] - suma maxima daca am selectat i culori si am j plusuri
        /// poz[i] - capetele stanga dreapta unde am ramas la fiecare culoare
        for (i=0;i<=n;i++)
            for (j=0;j<=n/2;j++)
                dp[i][j] = -INF, t[i][j] = 0;
        dp[0][0] = 0;

        for (i=1;i<=n;i++){
            while (ans[i-1][poz[i-1].first] != -1)
                poz[i-1].first++;
            while (ans[i-1][poz[i-1].second] != -1)
                poz[i-1].second--;

            for (int j=0;j<=n/2;j++){ /// vreau sa am j plusuri

                if (i - j > n/2) /// am prea multe minusuri
                    continue;

                /// iau din stanga => -
                if (dp[i-1][j] != -INF && dp[i-1][j] - x[i-1][poz[i-1].first] > dp[i][j]){

                    dp[i][j] = dp[i-1][j] - x[i-1][poz[i-1].first];
                    t[i][j] = 1;
                }
                /// iau din dreapta => +
                if (j && dp[i-1][j-1] != -INF && dp[i-1][j-1] + x[i-1][poz[i-1].second] > dp[i][j]){
                    dp[i][j] = dp[i-1][j-1] + x[i-1][poz[i-1].second];
                    t[i][j] = 0;
                }

            }

        }

        sum += dp[n][n/2];

        int idx = n, nr = n/2;
        while (idx){

            if (t[idx][nr])
                ans[idx-1][poz[idx-1].first] = pas;
            else {
                ans[idx-1][poz[idx-1].second] = pas;
                nr--;
            }

            idx--;
        }

    }

    allocate_tickets(ans);

    return sum;
}

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