제출 #244999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
244999		kshitij_sodani	Naan (JOI19_naan)	C++17	5 / 100	5 ms	384 KiB

naan

/*

*/
#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){
	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};
}
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;i++){
		for(llo j=0;j<n;j++){
			cost[j]={0,1};
		}
		llo kk=pos.a/pos.b;
		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(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.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};
					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){
				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;
}

컴파일 시 표준 에러 (stderr) 메시지

naan.cpp: In function 'int main()':
naan.cpp:45:7: warning: unused variable 'kk' [-Wunused-variable]
   llo kk=pos.a/pos.b;
       ^~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 24
• Subtask 3: 0 / 71