Submission #863726

# Submission time Handle Problem Language Result Execution time Memory
863726 2023-10-20T18:19:57 Z JakobZorz Carnival Tickets (IOI20_tickets) C++17
27 / 100
414 ms 86892 KB
#include"tickets.h"
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
using namespace std;
typedef long long ll;

ll find_maximum(int k,vector<vector<int>>x){
	ll n=x.size();
	ll m=x[0].size();
	vector<vector<int>>answer(n,vector<int>(m,-1));
    vector<vector<pair<ll,ll>>>arr(n,vector<pair<ll,ll>>(m));
    ll sum=0;
    vector<pair<ll,ll>>q;
    vector<ll>numplus(n,0);
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            arr[i][j]={x[i][j],j};
        }
        sort(arr[i].begin(),arr[i].end());
        for(ll j=0;j<k;j++){
            sum-=arr[i][j].first;
            q.emplace_back(arr[i][j].first+arr[i][m-k+j].first,i);
        }
    }
    sort(q.begin(),q.end());
    
    for(ll i=n*k-1;i>=n*k/2;i--){
        sum+=q[i].first;
        numplus[q[i].second]++;
    }
    vector<ll>numtaken1(n,0);
    vector<ll>numtaken2(n,0);
    
    for(int round=0;round<k;round++){
        int num_down=0;
        for(ll i=0;i<n;i++){
            if(num_down==n/2||numtaken1[i]==k-numplus[i]){
                numtaken2[i]++;
                answer[i][m-numtaken2[i]]=round;
            }else{
                answer[i][numtaken1[i]]=round;
                numtaken1[i]++;
                num_down++;
            }
        }
    }
    
	allocate_tickets(answer);
	return sum;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 17 ms 3932 KB Output is correct
6 Correct 414 ms 86892 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Contestant returned 5 but the tickets gives a total value of 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Contestant returned 23317133584 but the tickets gives a total value of 24057831018
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 2 ms 600 KB Contestant returned 174195330482 but the tickets gives a total value of 191909121109
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Incorrect 2 ms 600 KB Contestant returned 174195330482 but the tickets gives a total value of 191909121109
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 17 ms 3932 KB Output is correct
12 Correct 414 ms 86892 KB Output is correct
13 Incorrect 0 ms 348 KB Contestant returned 5 but the tickets gives a total value of 6
14 Halted 0 ms 0 KB -