제출 #621493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
621493		John3_141592	카니발 티켓 (IOI20_tickets)	C++14	11 / 100	1 ms	724 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define par pair<int,int>
#define f first
#define s second
#define ld long duble
#define ull unsigned long long
#define st short int

using namespace std;

ll find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector <pair<int,par>> vec;
	vector <vector<int>> answer;
	for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            vec.push_back({x[i][j],{i,j}});
        }
	}
	sort(vec.begin(),vec.end());
    deque <pair<int,par>> cola;
    for(auto i:vec) cola.push_back(i);
    bool vis[n+6];
    fill(vis,vis+n+3,false);
    ll solve=0;
    int asd[n][m];
    memset(asd,-1,sizeof(asd));
    for(int i=0;i<n/2;i++){
        pair<int,par> M1,M2,m1,m2;
        if(cola.size()==2){
            solve+=cola.back().f-cola.front().f;
            asd[cola.front().s.f][cola.front().s.s]=0;
            asd[cola.back().s.f][cola.back().s.s]=0;
            continue;
        }
        while(vis[cola.front().s.f]) cola.pop_front();
        while(vis[cola.back().s.f]) cola.pop_back();
        M1=cola.back(),cola.pop_back();
        m1=cola.front(),cola.pop_front();
        if(M1.s.f!=m1.s.f){
            solve+=M1.f-m1.f;
            asd[M1.s.f][M1.s.s]=0;
            asd[m1.s.f][m1.s.s]=0;
            vis[m1.s.f]=true;
            continue;
        }
        while(vis[cola.front().s.f]) cola.pop_front();
        while(vis[cola.back().s.f]) cola.pop_back();
        M2=cola.back(),cola.pop_back();
        m2=cola.back(),cola.pop_back();
        if(M1.f-m2.f>=M2.f-m1.f){
            solve+=M1.f-m2.f;
            asd[M1.s.f][M1.s.s]=0;
            asd[m2.s.f][m2.s.s]=0;
            vis[M1.s.f]=true;
            vis[m2.s.f]=true;
            continue;
        }
        solve+=M2.f-m1.f;
        asd[M2.s.f][M2.s.s]=0;
        asd[m1.s.f][m1.s.s]=0;
        vis[M2.s.f]=true;
        vis[m1.s.f]=true;
    }
    for(int i=0;i<n;i++){
        vector <int> aux;
        for(int j=0;j<m;j++){
            aux.push_back(asd[i][j]);
        }
        answer.push_back(aux);
    }
	allocate_tickets(answer);
	return solve;
}

• Subtask 1: 11 / 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