제출 #1233742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233742		CELD_07	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	313 ms	51692 KiB

tickets

#include "tickets.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	ll res1=0;
    vector<vector<int>> res(n, vector<int>(m, -1));
    vector<vector<pair<ll, ll>>> v(n), v1(n);
    priority_queue<tuple<ll, ll, ll, ll>> pq1;
    for(int i=0; i<n; i++){
    for(int j=0; j<k; j++){
    v[i].push_back({x[i][j], j});
    res[i][j]=j;
    res1-=x[i][j];
    }
    for(int j=m-k; j<m; j++){
    v1[i].push_back({x[i][j], j});
    }
    }
    for(int i=0; i<k; i++){
    priority_queue<tuple<ll, ll, ll, ll>>().swap(pq1);
    for(int j=0; j<n; j++){
    pq1.push({v[j].back().ft+v1[j].back().ft, v[j].back().sd, v1[j].back().sd, j});
    }
    for(int j=0; j<n/2; j++){
    ll o, o1, o2, o3;
    tie(o, o1, o2, o3)=pq1.top();
    pq1.pop();
    res1+=o;
    v[o3].pop_back();
    v1[o3].pop_back();
    //cout<<o<<" "<<o1<<" "<<o2<<" "<<o3<<endl;
    res[o3][o2]=i;
    if(o1<o2)res[o3][o1]=-1;
    }
    }
	allocate_tickets(res);
	/*for(int i=0; i<n; i++){
	for(int j=0; j<m; j++){
	cout<<res[i][j]<<" ";
	}
	cout<<endl;
	}*/
	return res1;
}/*
int main(){
cout<<find_maximum(1, {{9}, {4}, {6}, {7}})<<endl;
}
*/

• 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