이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define allv(V) (V).begin(),(V).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll operator * (pll a, pll b) { return a.fi*b.se - a.se*b.fi; }
pll B[2005][2005];
ll A[2005];
int C[2005];
int N, L;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> L;
for(int i = 0; i < N; i++) {
for(int j = 0; j < L; j++) {
ll x; cin >> x;
A[j+1] = A[j] + x;
}
ll S = A[L];
int k = 1, n = 0;
while(k < N) {
while(A[n+1]*N <= S*k) n++;
ll u = S*k - A[n]*N, d = (A[n+1]-A[n])*N;
B[i][k++] = {u + d*n, d};
}
}
vector<int> V(N); iota(allv(V), 0);
for(int k = 1; k < N; k++)
swap(V[k-1], *min_element(k-1+allv(V), [&](int a, int b) {
return B[a][k] * B[b][k] < 0;
}));
for(int k = 1; k < N; k++) {
pll p = B[V[k-1]][k];
cout << p.fi << ' ' << p.se << '\n';
}
for(int v : V) cout << v+1 << ' ';
cout << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |