Submission #1058544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058544		idas	Carnival Tickets (IOI20_tickets)	C++17	16 / 100	282 ms	108744 KiB

tickets

#include "tickets.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define le(x) ((x)[((int)(x).size())-1])
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MxN=1510, INF=1e9, LINF=1e18;
int n, m, l[MxN], r[MxN];
pii prv[MxN][MxN];
ll dp[MxN][MxN];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
    n=sz(x); m=sz(x[0]);

    assert(k==1);

    FOR(i, 1, n+1) {
        l[i]=x[i-1][0];
        r[i]=x[i-1][m-1];
    }

    FOR(i, 0, n+1) FOR(j, 0, n+1) dp[i][j]=-LINF, prv[i][j]={-1,-1};

    dp[0][0]=0;
    FOR(i, 1, n+1) {
        FOR(j, 0, i+1) {
            if(j>=1) {
                dp[i][j]=dp[i-1][j-1]+r[i];
                prv[i][j]={i-1,j-1};
            }
            if(dp[i-1][j]-l[i]>dp[i][j]) {
                dp[i][j]=dp[i-1][j]-l[i];
                prv[i][j]={i-1,j};
            }
        }
    }

    vector b(n, vector(m, -1));
    int i=n, j=n/2;
    while(i>0) {
        int x=prv[i][j].f, y=prv[i][j].s;

        assert(x!=-1 && y!=-1);

        if(y==j-1) b[i-1][m-1]=0;
        else b[i-1][0]=0;

        assert(x==i-1);

        i=x; j=y;
    }

    allocate_tickets(b);

    return dp[n][n/2];
}
/*
2 3 2
0 2 5
1 1 3

4 2 1
5 9
1 4
3 6
2 7

4 4 1
0 1 2 9
4 4 4 5
3 3 3 7
3 4 4 4

4 2 1
0 10
1 5
0 6
0 6

4 4 1
0 1 2 9
7 7 7 7
7 7 7 7
7 7 7 7

8 2 1
1 9
0 10
2 3
3 4
6 8
1 5
0 2
3 4

4 3 2
0 1 1
1 1 1
0 0 1
0 0 0

4 2 2
0 1
0 1
0 0
1 1

4 2 1
0 1
0 0
0 0
1 1

4 3 2
0 0 0
0 1 1
0 1 1
1 1 1
*/

Compilation message (stderr)

tickets.cpp:15:35: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int MxN=1510, INF=1e9, LINF=1e18;
      |                                   ^~~~

• Subtask 1: 0 / 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