Submission #1078975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078975		KaleemRazaSyed	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	390 ms	88908 KiB

tickets

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

using namespace std;

typedef long long ll;

long long find_maximum(int k, vector<vector<int> > d)
{
  int n = d.size(), m = d[0].size();
  vector<vector<int> > sol(n, vector<int> (m, -1));

  if(k == 1)
    {
      // assuming my k = 1
      int par[n + 1][n + 1];
      ll dp[n + 1][n + 1];
      for(int i = 0; i <= n; i ++)
	for(int j = 0; j <= n; j ++)
	  dp[i][j] = -1e18;
  
      dp[0][0] = 0;
  
      for(int i = 1; i <= n; i ++)
	for(int j = 0; j <= i; j++)
	  {
	    dp[i][j] = max(dp[i][j], dp[i - 1][j] - d[i - 1][0]);
	    par[i][j] = j;
	
	    if(j > 0 && dp[i][j] < dp[i - 1][j - 1] + d[i - 1].back())
	      dp[i][j] = dp[i - 1][j - 1] + d[i - 1].back(), par[i][j] = j - 1;
	  }

      int x = n / 2; // this is my initial state
      for(int i = n; i > 0; i--)
	{
	  if(par[i][x] == x)
	    sol[i - 1][0] = 0;
	  else
	    sol[i - 1].back() = 0, x--;
	}
    }
  else
    {
      vector<vector<int> > vec;
      for(int i = 0; i < n; i ++)
	for(int j = 0; j < m ; j ++)
	  vec.push_back({d[i][j], i, j});

      int cnt[n] = {};
      
      sort(vec.begin(), vec.end());
      for(int i = 0; i < vec.size() / 2; i ++)
	cnt[vec[i][1]]++;

      vector<pair<int,int> > c(n);
      for(int i = 0; i < n; i ++)
	c[i] = {cnt[i], i};

      sort(c.begin(), c.end());
      for(int i = 0; i < n / 2; i ++)
	{
	  for(int j = 0; j < m; j ++)
	    sol[c[i].second][j] = j;
	  for(int j = 0; j < m; j ++)
	    sol[c[n - i - 1].second][j] = m - j - 1;
	  
	}
      ll sm = 0;
      for(int i = 0; i < vec.size() / 2; i ++)
	sm -= vec[i][0];
      for(int i = vec.size() / 2; i < vec.size(); i ++)
	sm += vec[i][0];
      allocate_tickets(sol);
      return sm;
    }
  
  
  allocate_tickets(sol);

  vector<int > vec[k];
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < m; j ++)
      if(sol[i][j] != -1)
	vec[sol[i][j]].push_back(d[i][j]);

  ll ans = 0;
  for(int i = 0; i < k; i ++)
    {
      sort(vec[i].begin(), vec[i].end());
      int b = vec[i][vec[i].size() / 2];
      for(int j : vec[i])
	ans += abs(j - b);
    }
  return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |       for(int i = 0; i < vec.size() / 2; i ++)
      |                      ~~^~~~~~~~~~~~~~~~
tickets.cpp:70:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |       for(int i = 0; i < vec.size() / 2; i ++)
      |                      ~~^~~~~~~~~~~~~~~~
tickets.cpp:72:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |       for(int i = vec.size() / 2; i < vec.size(); i ++)
      |                                   ~~^~~~~~~~~~~~

• 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