Submission #1234885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234885		jsw	Carnival Tickets (IOI20_tickets)	C++20	0 / 100	3094 ms	584 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
using ll=long long;

ll find_maximum(int k, vector<vector<int>>x){
  int n,m; n=x.size(); m=x[0].size();
  vector<int>bplus(n), bminus(n);
  for(int i=0;i<n;i++)bplus[i]=m;
  for(int i=0;i<n;i++)bminus[i]=k;
  vector<vector<int>>wyn(n);
  for(int i=0;i<n;i++)wyn[i].resize(m);
  for(int i=0;i<n;i++)for(int j=0;j<m;j++)wyn[i][j]=0;
  priority_queue<pair<int,int>>pq;
  ll ans=0;
  for(int i=0;i<n;i++)for(int j=0;j<k;j++){
    ans-=x[i][j];
    wyn[i][j]=-1;
  }
  for(int i=0;i<n;i++)pq.push({x[i][m-1]+x[i][k-1],i});
  ll pom=0; pair<int,int>cur; int i;
  while(2*pom<n*k){
    cur=pq.top(); ans+=cur.first;
    pq.pop();
    i=cur.second;
    bplus[i]--; bminus[i]--;
    wyn[i][bminus[i]]=0;
    wyn[i][bplus[i]]=1;
    pom++;
    if(bminus[i]>0)pq.push({x[i][bminus[i]-1]+x[i][bplus[i]-1],i});
  }
  for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(wyn[i][j]==0)wyn[i][j]=-1;else if(wyn[i][j]==-1) wyn[i][j]=-2;else wyn[i][j]=1;}}
  int d=0,it=0; pom=-1; bool tab[n]; for(int i=0;i<n;i++)tab[i]=1; int all=0;
  vector<int>bpc;
  bpc=bplus;
  while(all<n){
    pom++; pom%=n;
    if(!tab[i])continue;
    if(bplus[pom]==m){
      all++;
      tab[pom]=0;
      continue;
    }
    wyn[pom][bplus[pom]]=d;
    bplus[pom]++;
    it++;
    if(2*it==n){
      it=0;
      d++;
    }
  }
  int j;
  for(int i=0;i<n;i++){
    j=0; it=bpc[i]; d=0;
    while(wyn[i][j]==-2){
      if(it==m)wyn[i][j]=d;
      else{
        if(wyn[i][it]==d){
          it++; d++; continue;
        }
        else wyn[i][j]=d;
      }
      d++;
      j++;
    }
  }
  allocate_tickets(wyn);
  return ans;
}

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