oj.uz

Submission #377401

# Submission time Handle Problem Language Result Execution time Memory
377401 2021-03-14T07:07:57 Z Thistle Carnival Tickets (IOI20_tickets) C++14
41 / 100
 711 ms 57708 KB 
#include "tickets.h"
#include <vector>
#include<algorithm>
#include<set>
#include<iostream>
#include<random>
#include<queue>
#include<cassert>
using namespace std;
using ll=long long;
using H=pair<ll, ll>;
#define vec vector
#define vi vec<ll>
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),0,(n))
#define siz(a) int((a).size())
#define fs first
#define sc second
constexpr ll inf=1e16;
constexpr ll Inf=1e9+1;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();


	std::vector<std::vector<int>> answer(n,vec<int>(m,-1));
	ll ans=0;

	if(m==1){
		vi v;
		rep(i,n) v.pb(x[i][0]);
		sort(all(v));
		rep(i,n){
			if(i<n/2) ans-=v[i];
			else ans+=v[i];
		}
		rep(i,n)rep(j,m) answer[i][j]=0;
	}
	else if(k==1){
		vec<int> mx(n,-Inf),mn(n,Inf);
		vec<int>mxi(n,-1),mni(n,-1);
		rep(i,n)rep(j,m){
			if(mx[i]<x[i][j]){
				mx[i]=max(mx[i],x[i][j]);
				mxi[i]=j;
			}
			if(mn[i]>x[i][j]){
				mn[i]=min(mn[i],x[i][j]);
				mni[i]=j;
			}
		}
		vec<vi> dp=vec<vi>(n+1,vi(n+1,-inf));
		dp[0][0]=0;
		rep(i,n)rep(j,n+1){
			if(dp[i][j]==inf) continue;
			dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+mx[i]);
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]-mn[i]);
		}
		ans=dp[n][n/2];
		ll k=dp[n][n/2];
		int c=n/2;
		for(int i=n-1;i>=0;i--){
			if(c>0&&dp[i][c-1]+mx[i]==k){
				answer[i][mxi[i]]=0;
				c--;
				k=dp[i][c];
			}
			else if(dp[i][c]-mn[i]==k){
				answer[i][mni[i]]=0;
				k=dp[i][c];
			}
		}
	}
	else{
		priority_queue<H>p;
		vi one(n,0);
		rep(i,n)rep(j,m) if(x[i][j]==1) one[i]++;
		rep(i,n) p.push(H{one[i],i});
		vi fst(n,0),lst(n,m-1);
		rep(iter,k){
			vi v;
			vec<bool>used(n,0);
			rep(i,n/2){
				v.pb(p.top().sc);
				used[p.top().sc]=1;
				p.pop();
			}
			int cnt1=0,cnt0=0;
			rep(i,n){
				if(used[i]){
					if(one[i]>0) {
						cnt1++,one[i]--;
						answer[i][lst[i]--]=iter;
					}
					else{
						 cnt0++;
						 answer[i][fst[i]++]=iter;
					}
				}
				else{
					if(m-iter-one[i]>0) {
						cnt0++;
						answer[i][fst[i]++]=iter;
					}
					else{
						 cnt1++,one[i]--; 
						 answer[i][lst[i]--]=iter;
					}
				}
			}
			ans+=min(cnt0,cnt1);
			for(auto g:v) p.push(H{one[g],g});
		}
	}
	
	allocate_tickets(answer);
	return ans;
}

Compilation message

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:34:3: note: in expansion of macro 'rep'
   34 |   rep(i,n) v.pb(x[i][0]);
      |   ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:36:3: note: in expansion of macro 'rep'
   36 |   rep(i,n){
      |   ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:40:3: note: in expansion of macro 'rep'
   40 |   rep(i,n)rep(j,m) answer[i][j]=0;
      |   ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:40:11: note: in expansion of macro 'rep'
   40 |   rep(i,n)rep(j,m) answer[i][j]=0;
      |           ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:45:3: note: in expansion of macro 'rep'
   45 |   rep(i,n)rep(j,m){
      |   ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:45:11: note: in expansion of macro 'rep'
   45 |   rep(i,n)rep(j,m){
      |           ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:57:3: note: in expansion of macro 'rep'
   57 |   rep(i,n)rep(j,n+1){
      |   ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:57:11: note: in expansion of macro 'rep'
   57 |   rep(i,n)rep(j,n+1){
      |           ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:80:3: note: in expansion of macro 'rep'
   80 |   rep(i,n)rep(j,m) if(x[i][j]==1) one[i]++;
      |   ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:80:11: note: in expansion of macro 'rep'
   80 |   rep(i,n)rep(j,m) if(x[i][j]==1) one[i]++;
      |           ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:81:3: note: in expansion of macro 'rep'
   81 |   rep(i,n) p.push(H{one[i],i});
      |   ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'iter' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:83:3: note: in expansion of macro 'rep'
   83 |   rep(iter,k){
      |   ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:86:4: note: in expansion of macro 'rep'
   86 |    rep(i,n/2){
      |    ^~~
tickets.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
tickets.cpp:17:18: note: in expansion of macro 'rng'
   17 | #define rep(i,n) rng((i),0,(n))
      |                  ^~~
tickets.cpp:92:4: note: in expansion of macro 'rep'
   92 |    rep(i,n){
      |    ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 768 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 28 ms 2456 KB Output is correct
6 Correct 711 ms 51496 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 25 ms 2540 KB Output is correct
6 Correct 620 ms 56812 KB Output is correct
7 Correct 655 ms 57272 KB Output is correct
8 Correct 5 ms 620 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 10 ms 876 KB Output is correct
13 Correct 21 ms 2284 KB Output is correct
14 Correct 24 ms 2284 KB Output is correct
15 Correct 651 ms 57708 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 28 ms 2456 KB Output is correct
12 Correct 711 ms 51496 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 3 ms 492 KB Output is correct
17 Correct 25 ms 2540 KB Output is correct
18 Correct 620 ms 56812 KB Output is correct
19 Correct 655 ms 57272 KB Output is correct
20 Correct 5 ms 620 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 10 ms 876 KB Output is correct
25 Correct 21 ms 2284 KB Output is correct
26 Correct 24 ms 2284 KB Output is correct
27 Correct 651 ms 57708 KB Output is correct
28 Incorrect 1 ms 364 KB Contestant returned 5 but the tickets gives a total value of 0
29 Halted 0 ms 0 KB -