oj.uz

Submission #863725

# Submission time Handle Problem Language Result Execution time Memory
863725 2023-10-20T18:17:53 Z JakobZorz Carnival Tickets (IOI20_tickets) C++14
27 / 100
 426 ms 86788 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;
}

Subtask #1
11.0 / 11.0

# 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 1 ms 420 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 18 ms 3788 KB Output is correct
6 Correct 426 ms 86788 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Contestant returned 5 but the tickets gives a total value of 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 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 1 ms 344 KB Contestant returned 23317133584 but the tickets gives a total value of 24057831018
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Incorrect 2 ms 604 KB Contestant returned 174195330482 but the tickets gives a total value of 191909121109
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Incorrect 2 ms 604 KB Contestant returned 174195330482 but the tickets gives a total value of 191909121109
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 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 1 ms 420 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 18 ms 3788 KB Output is correct
12 Correct 426 ms 86788 KB Output is correct
13 Incorrect 0 ms 344 KB Contestant returned 5 but the tickets gives a total value of 6
14 Halted 0 ms 0 KB -