| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 747110 | Rafi22 | Carnival Tickets (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000002022;
int inf=1000000007;
ll infl=1000000000000000007;
/*void allocate_tickets(vector<vector<int>>r)
{
int n=sz(r),m=sz(r[0]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++) cout<<r[i][j]<<" ";
cout<<endl;
}
}*/
ll find_maximum(int k,vector<vector<ll>>a)
{
int n=sz(a),m=sz(a[0]);
vector<pair<int,pair<int,int>>>V;
vector<vector<int>>r(n,vector<int>(m,-1));
ll sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++) V.pb({a[i][j],{i,j}});
for(int j=m-k;j<m;j++) sum+=a[i][j];
}
sort(all(V));
set<pair<int,pair<int,int>>>good,bad;
ll ans=-infl,act=0;
int ile=n*k/2,ii,jj;
for(auto [q,p]:V)
{
int i=p.st,j=p.nd;
if(j<k)
{
act+=-a[i][j]-a[i][m-k+j];
good.insert({-a[i][j]-a[i][m-k+j],{i,j}});
}
if(j>=m-k)
{
ile--;
if(!good.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}}))
{
bad.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}});
act+=-a[i][j]-a[i][j-m+k];
}
}
if(ile<0) break;
while(sz(good)>ile)
{
act-=(*good.begin()).st;
bad.insert(*good.begin());
good.erase(*good.begin());
}
while(sz(bad)>0&&sz(good)<ile)
{
act+=(*--bad.end()).st;
good.insert(*--bad.end());
bad.erase(*--bad.end());
}
if(sz(good)==ile&&act>ans)
{
ans=act;
ii=i;
jj=j;
}
}
good.clear(),bad.clear();
ile=n*k/2;
vector<int>X(n,-1),Y(n,m-k);
for(auto [q,p]:V)
{
int i=p.st,j=p.nd;
if(j<k)
{
good.insert({-a[i][j]-a[i][m-k+j],{i,j}});
}
if(j>=m-k)
{
ile--;
X[i]++;
Y[i]--;
if(!good.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}}))
{
bad.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}});
}
}
if(ile<0) break;
while(sz(good)>ile)
{
act-=(*good.begin()).st;
bad.insert(*good.begin());
good.erase(*good.begin());
}
while(sz(bad)>0&&sz(good)<ile)
{
act+=(*--bad.end()).st;
good.insert(*--bad.end());
bad.erase(*--bad.end());
}
if(i==ii&&j==jj)
{
for(auto x:good)
{
X[x.nd.st]++;
Y[x.nd.st]++;
}
break;
}
}
for(int j=0;j<k;j++)
{
int c1=n/2,c2=n/2;
for(int i=0;i<n;i++)
{
if(X[i]==-1)
{
c2--;
r[i][Y[i]]=j;
Y[i]++;
}
else if(Y[i]==m)
{
c1--;
r[i][X[i]]=j;
X[i]--;
}
}
for(int i=0;i<n;i++)
{
if(X[i]!=-1&&c1>0)
{
c1--;
r[i][X[i]]=j;
X[i]--;
}
else
{
c2--;
r[i][Y[i]]=j;
Y[i]++;
}
}
}
allocate_tickets(r);
return ans+sum;
}