oj.uz

답안 #245011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245011 2020-07-05T10:58:43 Z kshitij_sodani Naan (JOI19_naan) C++17
0 / 100
 4000 ms 384 KB 
/*

*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
llo n,l;
llo aa[2001][2001];
pair<llo,llo> cost[2001];
llo su[2001];
pair<llo,llo> add(pair<llo,llo> cur,llo ind,pair<llo,llo> pos){
	/*if(pos.b==0){
		while(true){
			continue;
		}
	}*/
	pair<llo,llo> val={aa[ind][pos.a/pos.b]*(pos.b-(pos.a%pos.b)),pos.b};
	return {cur.a*val.b+cur.b*val.a,val.b*cur.b};
}
llo gcd(llo aa,llo bb){
	if(aa==0){
		return bb;
	}
	return gcd(bb%aa,aa);
}
pair<llo,llo> simp(pair<llo,llo> aa){
	llo cc=gcd(aa.a,aa.b);
	return {aa.a/cc,aa.b/cc};
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>l;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<l;j++){
			cin>>aa[i][j];
			su[i]+=aa[i][j];
		}
	}
	set<llo> cur;
	for(llo i=0;i<n;i++){
		cur.insert(i);
	}
	vector<llo> ans;
	vector<pair<llo,llo>> ans2;
	pair<llo,llo> pos={0,1};
	for(llo i=0;i<n-1;i++){
		for(llo j=0;j<n;j++){
			cost[j]={0,1};
		}
		llo ans5=-1;
		while(true){
			llo st=0;
			pair<llo,llo> mi={-1,-1};
			//cout<<pos.a<<","<<pos.b<<endl;
			for(auto j:cur){
				pair<llo,llo> x=add(cost[j],j,pos);
				//cout<<j<<":"<<x.a<<":"<<x.b<<endl;
				if(pos.a/pos.b>=n){
					while(true){
						continue;
					}
				}
				if(x.a*n>=x.b*su[j]){
					pair<llo,llo> tt={su[j]*cost[j].b-cost[j].a*n,n*cost[j].b};
					tt=simp(tt);
			/*		if(pos.b==0){
						while(true){
							continue;
						}
					}
*/	
					tt.b*=aa[j][pos.a/pos.b];

				//	cout<<tt.a<<":"<<tt.b<<endl;
					tt={tt.a*pos.b+tt.b*pos.a,pos.b*tt.b};
					tt=simp(tt);
					if(mi.a==-1){
						mi=tt;
						st=j+1;
					}
					else{
						if(tt.a*mi.b<tt.b*mi.a){
							st=j+1;
							mi=tt;
						}
					}
					continue;
				}
				cost[j]=x;
			}

			if(st>0){
				/*if(mi.b==0){
					while(true){
						continue;
					}
				}*/
				pos=simp(mi);

				ans5=st;
				break;
			}
			pos.a+=pos.b-(pos.a%pos.b);
		}

		ans.pb(ans5);
		cur.erase(ans5-1);
		if(i<n-1){
			ans2.pb(pos);
		}
	}
	for(auto j:ans2){
		cout<<j.a<<" "<<j.b<<endl;
	}
	for(auto j:ans){
		cout<<j<<" ";
	}
	cout<<endl;
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4088 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4090 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4088 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -