제출 #703807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703807		Darren0724	Naan (JOI19_naan)	C++17	100 / 100	374 ms	125956 KiB

naan

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int INF=1e18;
bool operator<(pair<int,int> a,pair<int,int> b){
    return (__int128)a.first*b.second<(__int128)a.second*b.first;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    vector<int> a(n);
    vector<vector<int>> v(n,vector<int>(m)),pre(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>v[i][j];
            v[i][j]*=n;
            a[i]+=v[i][j];
        }
        a[i]/=n;
    }
    for(int i=0;i<n;i++){
        pre[i][0]=v[i][0];
        for(int j=1;j<m;j++){
            pre[i][j]=pre[i][j-1]+v[i][j];
        }
    }
    vector<bool> vis(n);
    vector<vector<pair<int,int>>> rec(n,vector<pair<int,int>>(n));
    for(int i=0;i<n;i++){
        int need=0;
        int ptr=0;
        for(int j=0;j<n-1;j++){
            need+=a[i];
            while(ptr<m&&pre[i][ptr]<need){
                ptr++;
            }
            int p=(ptr>0?pre[i][ptr-1]:0);
            rec[i][j]={need-p+ptr*v[i][ptr],v[i][ptr]};
        }
    }
    vector<int> ans(n);
    for(int i=0;i<n-1;i++){
        int idx=-1;
        for(int j=0;j<n;j++){
            if(vis[j]){
                continue;
            }
            if(idx==-1){
                idx=j;
            }
            else if(rec[j][i]<rec[idx][i]){
                idx=j;
            }
        }
        ans[i]=idx+1;
        vis[idx]=1;
        cout<<rec[idx][i].first<<' '<<rec[idx][i].second<<endl;
    }
    for(int i=0;i<n;i++){
        if(vis[i]==0){
            ans[n-1]=i+1;
        }
    }
    for(int j=0;j<n;j++){
        cout<<ans[j]<<' ';
    }
    return 0;
}

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