Submission #1291689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291689		julia_08	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	275 ms	72416 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"

using ll = long long;

using namespace std;

const int MAXN = 1510;
const ll INF = 1e18;

ll mn[MAXN], mx[MAXN];

ll dp[MAXN][MAXN];

ll find_maximum(int k, vector<vector<int>> x){

	int n = x.size();
	int m = x[0].size();

	vector<vector<int>> ans;

	for(int i=0; i<n; i++){
		ans.push_back({});
	  for(int j=0; j<m; j++) ans[i].push_back(-1);
	}

  for(int i=0; i<=n; i++){
    for(int j=0; j<=n; j++){
      dp[i][j] = -INF;
    }
  }

  dp[0][0] = 0;

  for(int i=1; i<=n; i++){

    int mn = x[i - 1][0], mx = x[i - 1][m - 1];

    for(int j=0; j<=(n / 2); j++){

      dp[i][j] = dp[i - 1][j] + mx;
      if(j > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] - mn);

    }

  }

  int cur = n / 2;

  for(int i=n; i>=1; i--){

    int mn = x[i - 1][0], mx = x[i - 1][m - 1];

    if(cur == 0 || dp[i - 1][cur] + mx == dp[i][cur]){

      ans[i - 1][m - 1] = 0;

    } else{

      ans[i - 1][0] = 0;
      cur --;

    }

  }

	allocate_tickets(ans);

	return dp[n][n / 2];

}

• 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