제출 #1136518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136518		byunjaewoo	Naan (JOI19_naan)	C++20	29 / 100	106 ms	54080 KiB

naan

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=2010;
int n, l, a[N][N], sum[N], ans2[N];
pair<int, int> p[N][N];
bool chk[N];
vector<pair<int, int>> ans;

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>>a[i][j], sum[i]+=a[i][j], a[i][j]*=n;
    }
    for(int i=1; i<=n; i++) {
        int q=1, v=0;
        for(int j=1; j<n; j++) {
            int cur=0;
            while(q<l && a[i][q]-v<=sum[i]-cur) cur+=a[i][q]-v, q++, v=0;
            v+=sum[i]-cur;
            p[i][j]={a[i][q]*(q-1)+v, a[i][q]};
        }
        p[i][n]={l, 1};
    }
    pair<int, int> prev={0, 1};
    for(int i=1, j=0; i<=n; i++) {
        int t=0;
        pair<int, int> mn={N*N, 1};
        for(int k=1; k<=n; k++) if(!chk[k] && mn.first*p[k][i].second>mn.second*p[k][i].first) {
            if(prev.first*p[k][i].second<prev.second*p[k][i].first) mn=p[k][i], t=k;
        }
        prev=mn;
        ans.push_back(mn), ans2[i]=t, chk[t]=true;
    }
    ans.pop_back();
    for(auto i:ans) cout<<i.first<<" "<<i.second<<"\n";
    for(int i=1; i<=n; i++) cout<<ans2[i]<<" ";
    return 0;
}

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