Submission #370034

#TimeUsernameProblemLanguageResultExecution timeMemory
370034azberjibiouNaan (JOI19_naan)C++17
0 / 100
2 ms500 KiB
#include <bits/stdc++.h> #define gibon ios::sync_with_stdio(false); cin.tie(0); using namespace std; #define fir first #define sec second #define ll long long #define pii pair<int, int> const int mxN=2020; typedef struct frac{ ll ja, mo; }frac; ll N, L; ll V[mxN][mxN]; frac ans[mxN][mxN]; ll sum[mxN]; bool Chk[mxN]; queue <int> que; frac mnus(frac a, frac b) { frac res={a.ja*b.mo-a.mo*b.ja, a.mo*b.mo}; if(res.mo<0) res.mo*=-1, res.ja*=-1; return res; } bool cmp(frac a, frac b) { return mnus(a, b).ja<0; } int main() { gibon cin >> N >> L; for(int i=1;i<=N;i++) for(int j=1;j<=L;j++) cin >> V[i][j]; for(int i=1;i<=N;i++) for(int j=1;j<=L;j++) sum[i]+=V[i][j]; for(int i=1;i<=N;i++) { int now=0; int cnt=1; for(int j=1;j<=N;j++) { ll tot=sum[i]; while(tot>N*V[i][cnt]-now) { tot-=N*V[i][cnt]-now; now=0; cnt++; } now+=tot; ans[i][j].mo=N*V[i][cnt]; ans[i][j].ja=now+ans[i][j].mo*(cnt-1); } } for(int i=1;i<N;i++) { int pos=-1; for(int j=1;j<=N;j++) { if(Chk[j]) continue; if(pos==-1) pos=j; else if(cmp(ans[i][j], ans[i][pos])) pos=j; } cout << ans[i][pos].ja << " " << ans[i][pos].mo << '\n'; que.push(pos); Chk[pos]=true; } for(int i=1;i<=N;i++) if(!Chk[i]) que.push(i); while(!que.empty()) { cout << que.front() << " "; que.pop(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...