oj.uz

Submission #521475

# Submission time Handle Problem Language Result Execution time Memory
521475 2022-02-02T08:18:50 Z errorgorn Akcija (COCI21_akcija) C++17
60 / 110
 5000 ms 63520 KB 
// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
ii arr[2005];
ll w[2005];
ll d[2005];

ii memo[2005][2005];
ii dp(int i,int j){
	if (i==n) return {0,0};
	if (memo[i][j]!=ii(-1,-1)) return memo[i][j];
	
	ii res=dp(i+1,j);
	if (j<d[i]){
		ii temp=dp(i+1,j+1);
		temp.fi++,temp.se+=w[i];
		res=max(res,temp);
	}
	
	return memo[i][j]=res;
}

vector<ii> ans;
void search(int i,int j,ll num,ll tot){
	if (i==n){
		if (ii(num,tot)<ii(0,0)) ans.pub({num,tot});
		return;
	}
	
	if (dp(i,j)<ii(num,tot)) return;
	
	search(i+1,j,num,tot);
	if (sz(ans)==k) return;
	if (j<d[i]) search(i+1,j+1,num-1,tot-w[i]);
}

bool smaller(ll num,ll tot){
	ans.clear();
	search(0,0,num,tot);
	
	return sz(ans)<k;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k;
	
	const int pad=1e9;
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
	sort(arr,arr+n,[](ii i,ii j){
		return i.se<j.se;
	});
	
	rep(x,0,n) tie(w[x],d[x])=arr[x];
	rep(x,0,n) w[x]=pad-w[x];
	
	memset(memo,-1,sizeof(memo));
	
	ll hi=2e16,lo=-1,mi;
	ll mxw=2e9*2000;
	
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		ll num=mi/mxw,tot=mi%mxw;
		//cout<<"bsta: "<<num<<" "<<tot<<endl;
		if (smaller(num,tot)) hi=mi;
		else lo=mi;
	}
	
	ll num=hi/mxw,tot=hi%mxw;
	//cout<<"debug: "<<num<<" "<<tot<<endl;
	
	ans.clear();
	search(0,0,num,tot);
	
	for (auto &it:ans) it={num-it.fi,tot-it.se};
	
	sort(all(ans));
	reverse(all(ans));
	
	while (sz(ans)<k) ans.pub({num,tot});
	
	for (auto &it:ans){
		cout<<it.fi<<" "<<it.fi*pad-it.se<<endl;
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:103:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |   mi=hi+lo>>1;
      |      ~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5075 ms 63392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5075 ms 63392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 63428 KB Output is correct
2 Correct 66 ms 63360 KB Output is correct
3 Correct 67 ms 63320 KB Output is correct
4 Correct 56 ms 63320 KB Output is correct
5 Correct 59 ms 63436 KB Output is correct
6 Correct 28 ms 63436 KB Output is correct
7 Correct 33 ms 63520 KB Output is correct
8 Correct 30 ms 63488 KB Output is correct
9 Correct 30 ms 63440 KB Output is correct
10 Correct 39 ms 63448 KB Output is correct
11 Correct 29 ms 63172 KB Output is correct
12 Correct 26 ms 63140 KB Output is correct
13 Correct 27 ms 63248 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 63328 KB Output is correct
2 Correct 33 ms 63256 KB Output is correct
3 Correct 36 ms 63308 KB Output is correct
4 Correct 36 ms 63316 KB Output is correct
5 Correct 31 ms 63308 KB Output is correct
6 Correct 33 ms 63196 KB Output is correct
7 Correct 31 ms 63244 KB Output is correct
8 Correct 39 ms 63260 KB Output is correct
9 Correct 33 ms 63332 KB Output is correct
10 Correct 29 ms 63172 KB Output is correct
11 Correct 29 ms 63156 KB Output is correct
12 Correct 27 ms 63120 KB Output is correct
13 Correct 33 ms 63308 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63148 KB Output is correct
2 Correct 29 ms 63244 KB Output is correct
3 Correct 37 ms 63176 KB Output is correct
4 Correct 29 ms 63156 KB Output is correct
5 Correct 32 ms 63216 KB Output is correct
6 Correct 37 ms 63148 KB Output is correct
7 Correct 30 ms 63212 KB Output is correct
8 Correct 28 ms 63196 KB Output is correct
9 Correct 31 ms 63152 KB Output is correct
10 Correct 30 ms 63200 KB Output is correct
11 Correct 24 ms 63172 KB Output is correct
12 Correct 27 ms 63124 KB Output is correct
13 Correct 26 ms 63268 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5075 ms 63392 KB Time limit exceeded
2 Halted 0 ms 0 KB -