Submission #1114961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114961		epicci23	Carnival Tickets (IOI20_tickets)	C++17	14 / 100	371 ms	90312 KiB

tickets

#include "bits/stdc++.h"
#include "tickets.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;

const ll N = 2500;

ll find_maximum(int _k, vector<vector<int>> _x){
  ll n=sz(_x),m=sz(_x[0]),k=_k;
  ll ar[n+5][m+5],l[n+5],r[n+5],ans=0;

  vector<vector<int>> ANS(n,vector<int>(m,-1));

  for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) ar[i][j] = _x[i-1][j-1];

  vector<int> cnt[n+5][2];

  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++) cnt[i][ar[i][j]].push_back(j);
  }

  vector<int> hm;
  for(int i=1;i<=n;i++) hm.push_back(i);

  for(int i=0;i<k;i++){
   int p = n;
   sort(all(hm),[&](int a,int b){
     return sz(cnt[a][1]) > sz(cnt[b][1]);
   });
   for(int j=0;j<n;j++){
    int c = hm[j];
    if(p>n/2){
      if(sz(cnt[c][1])){
        ans++;
        ANS[c-1][cnt[c][1].back()-1]=i;
        cnt[c][1].pop_back();
      }
      else{
        ANS[c-1][cnt[c][0].back()-1]=i;
        cnt[c][0].pop_back();
      }
    }
    else{
      if(sz(cnt[c][0])){
        ANS[c-1][cnt[c][0].back()-1]=i;
        cnt[c][0].pop_back();
      }
      else{
        ANS[c-1][cnt[c][1].back()-1]=i;
        cnt[c][1].pop_back();
        ans--;
      }
    }
    p--;
   }
  }

  allocate_tickets(ANS);
  return ans;
}

/*void _(){
  ll n,m,k;
  cin >> n >> m >> k;
  vector<vector<int>> ar(n,vector<int>(m,-1));
  for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin >> ar[i-1][j-1];

  cout << find_maximum(k,ar) << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  ll tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:12:19: warning: unused variable 'l' [-Wunused-variable]
   12 |   ll ar[n+5][m+5],l[n+5],r[n+5],ans=0;
      |                   ^
tickets.cpp:12:26: warning: unused variable 'r' [-Wunused-variable]
   12 |   ll ar[n+5][m+5],l[n+5],r[n+5],ans=0;
      |                          ^

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