제출 #375643

#제출 시각아이디문제언어결과실행 시간메모리
375643casperwangNaan (JOI19_naan)C++14
100 / 100
1409 ms130156 KiB
#include <bits/stdc++.h> #define int long long #define ll __int128 #define pii pair<int,int> #define ppi pair<pii,int> #define ff first #define ss second using namespace std; #define debug(args...) kout("[ " + string(#args) + " ]", args) void kout() { cerr << endl; } template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); } template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; } const int MAXN = 2000; const int INF = 1e9; int n, L; int v[MAXN+1][MAXN+1]; int pre[MAXN+1][MAXN+1]; int sum[MAXN+1]; pii arr[MAXN+1][MAXN+1]; bool vis[MAXN+1]; pii ans[MAXN]; int p[MAXN+1]; pii operator - (pii a, pii b) { int k = a.ss / __gcd(a.ss, b.ss) * b.ss; int c = __gcd(a.ff * (k / a.ss) - b.ff * (k / b.ss), k); return pii((a.ff * (k / a.ss) - b.ff * (k / b.ss)) / c, k / c); } pii operator + (pii a, pii b) { int k = a.ss / __gcd(a.ss, b.ss) * b.ss; int c = __gcd(a.ff * (k / a.ss) + b.ff * (k / b.ss), k); return pii((a.ff * (k / a.ss) + b.ff * (k / b.ss)) / c, k / c); } pii operator * (pii a, int b) { int k = __gcd(a.ss, b); return pii(a.ff * b / k, a.ss / k); } pii operator / (pii a, int b) { int k = __gcd(a.ff, b); return pii(a.ff / k, a.ss * b / k); } bool operator >= (pii a, pii b) { return (ll)a.ff * b.ss >= (ll)b.ff * a.ss; } signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> n >> L; for (int i = 1; i <= n; i++) { for (int j = 1; j <= L; j++) { cin >> v[i][j]; pre[i][j] = pre[i][j-1] + v[i][j]; sum[i] += v[i][j]; } } for (int i = 1; i <= n; i++) { int id = 1; for (int j = 1; j <= n; j++) { pii k(sum[i] * j, n); while (true) { if (pii(pre[i][id], 1) >= k) { arr[i][j] = (k - pii(pre[i][id-1], 1)) / v[i][id]; arr[i][j] = arr[i][j] + pii(id-1, 1); break; } else { id++; } } } } ans[0] = pii(0, 1); for (int i = 1; i <= n; i++) { ppi mmin(pii(INF, 0), 0); for (int j = 1; j <= n; j++) { if (vis[j]) continue; assert(arr[j][i] >= ans[i-1]); if (mmin.ff >= arr[j][i]) mmin = ppi(arr[j][i], j); } vis[mmin.ss] = true; p[i] = mmin.ss; if (i < n) ans[i] = mmin.ff; } for (int i = 1; i < n; i++) cout << ans[i].ff << ' ' << ans[i].ss << '\n'; for (int i = 1; i <= n; i++) cout << p[i] << " \n"[i==n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...