Submission #1191505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191505		Ak_16	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	705 ms	80872 KiB

tickets

#include <iostream>
#include "tickets.h"
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long

int n,m;
int k;
vector<vector<int>> s,y;
int l[2000];
int r[2000];
int now[2000];
int hat[2000];
ll tot;


struct rem{
  int col;
  int ind;
};

rem nik[2500000];

bool cmp(rem al, rem be){
  return y[al.col][al.ind-1] + y[al.col][al.ind-1+m-k] < y[be.col][be.ind-1] + y[be.col][be.ind-1+m-k];
}

bool cmp2(int ga, int de){
  return hat[ga] > hat[de];
}


ll find_maximum(int ka, vector<vector<int>> x){
  n = x.size();
  m = x[0].size();
  tot=0;
  k=ka;
  y = x;
  s = x;
  
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      s[i][j]=-1;
    }
  }
  
  for(int i=0; i<n; i++){
    l[i]=0;
    r[i]=m-1;
  }
  
  for(int i=0; i<n; i++){
    for(int j=1; j<=k; j++){
      nik[(i*k) + j].col = i;
      nik[(i*k) + j].ind = j;
    }
  }
  
  sort(nik+1, nik+n*k+1, cmp);
  
  for(int i=0; i<n; i++){
    hat[i]=0;
  }
  
  for(int i=1; i<=n*k/2; i++){
    hat[nik[i].col]++;
  }
  
  for(int ro=0; ro<k; ro++){
    
    for(int i=0; i<n; i++){
      now[i]=i;
    }
    
    sort(now, now+n, cmp2);
    
    for(int i=n/2; i<n; i++){
      tot += y[now[i]][r[now[i]]];
      s[now[i]][r[now[i]]] = ro;
      r[now[i]]--;
    }
    
    for(int i=0; i<n/2; i++){
      tot -= y[now[i]][l[now[i]]];
      hat[now[i]]--;
      s[now[i]][l[now[i]]] = ro;
      l[now[i]]++;
    }
    
  }
  
  
  
  allocate_tickets(s);
  
  return tot;
  
}

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