oj.uz

Submission #971127

# Submission time Handle Problem Language Result Execution time Memory
971127 2024-04-28T03:12:47 Z 12345678 Carnival Tickets (IOI20_tickets) C++17
27 / 100
 3000 ms 108624 KB 
#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1505;

pair<ll, int> dp[nx][nx];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	ll n = x.size(), ans=0, cnt=0;
	ll m = x[0].size(), l[nx], r[nx];
	vector<vector<int>> res(n, vector<int> (m, -1));
    for (int i=1; i<=n; i++) l[i]=0, r[i]=m-1;
    for (int i=1; i<=n; i++) dp[0][i].first=-1e18;
    while (k--)
    {
        for (int i=1; i<=n; i++)
        {
            for (int j=0; j<=i; j++)
            {
                dp[i][j].first=-1e18;
                if (j!=0) dp[i][j]=max(dp[i][j], {dp[i-1][j-1].first-x[i-1][l[i]], 1});
                if (j!=i) dp[i][j]=max(dp[i][j], {dp[i-1][j].first+x[i-1][r[i]], 0});
            }
        }
        auto cur=dp[n][n/2];
        int cj=n/2;
        for (int i=n; i>=1; i--)
        {
            if (cur.second) res[i-1][l[i]++]=cnt;
            else res[i-1][r[i]--]=cnt;
            if (cur.second) cur=dp[i-1][--cj];
            else cur=dp[i-1][cj];
        }
        ans+=dp[n][n/2].first;
        cnt++;
    }
	allocate_tickets(res);
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 17 ms 35932 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 17 ms 11612 KB Output is correct
6 Correct 393 ms 108624 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2504 KB Output is correct
5 Correct 39 ms 10836 KB Output is correct
6 Correct 2929 ms 92040 KB Output is correct
7 Execution timed out 3101 ms 66848 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 17 ms 35932 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 17 ms 11612 KB Output is correct
12 Correct 393 ms 108624 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 2 ms 2504 KB Output is correct
17 Correct 39 ms 10836 KB Output is correct
18 Correct 2929 ms 92040 KB Output is correct
19 Execution timed out 3101 ms 66848 KB Time limit exceeded
20 Halted 0 ms 0 KB -