제출 #378347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378347		cheissmart	Naan (JOI19_naan)	C++14	100 / 100	450 ms	93444 KiB

naan

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2002;

int a[N][N], sum[N];
pair<ll, ll> r[N][N];
int n, l;

bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
	return a.F * (b.S / n) < (a.S / n) * b.F;
}

signed main()
{
	IO_OP;
	
	cin >> n >> l;
	for(int i = 0; i < n; i++) {
		int sum = 0;
		for(int j = 0; j < l; j++) {
			cin >> a[i][j];
			sum += a[i][j];
			a[i][j] *= n;
		}
		int ptr = 0;
		ll cur = 0;
		for(int j = 1; j < n; j++) {
			ll need = (ll) sum * j;
			while(cur + a[i][ptr] <= need) {
				cur += a[i][ptr];
				ptr++;
			}
			r[i][j - 1] = {(ll) ptr * a[i][ptr] + need - cur, a[i][ptr]};
		}
	}
	vi p(n), vis(n);
	for(int i = 0; i < n - 1; i++) {
		int bestj = -1;
		for(int j = 0; j < n; j++) if(!vis[j]) {
			if(bestj == -1 || cmp(r[j][i], r[bestj][i])) {
				bestj = j;
			}
		}
		vis[bestj] = 1;
		p[i] = bestj;
		cout << r[bestj][i].F << " " << r[bestj][i].S << '\n';
	}
	for(int i = 0; i < n; i++) if(!vis[i])
		p[n - 1] = i;
	for(int i = 0; i < n; i++)
		cout << p[i] + 1 << ' ';

}

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