제출 #1234791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234791		jsw	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	304 ms	51344 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(i=0;i<n;i++){
    pom=0;
    for(int j=0;j<m;j++){
      if(wyn[i][j]==0)wyn[i][j]=-1;
      else if(i%2==0){
        wyn[i][j]=pom;
        pom++;
      }
      else{
        wyn[i][j]=k-1-pom;
        pom++;
      }
    }
  }
  allocate_tickets(wyn);
  return ans;
}

• 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