Submission #210448

#	Time	Username	Problem	Language	Result	Execution time	Memory
210448		mhy908	Naan (JOI19_naan)	C++14	100 / 100	631 ms	116852 KiB

naan

#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pll;
const LL llinf=1987654321987654321;
int n, m, pr[2010];
pll ans[2010][2010];
LL arr[2010][2010];
bool ch[2010];
bool operator<(pll a, pll b){
    return (__int128)a.F*b.S<(__int128)a.S*b.F;
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++)scanf("%lld", &arr[i][j]);
    }
    for(int i=1; i<=n; i++){
        LL sum=0, temp=arr[i][1];
        int pv=1;
        for(int j=1; j<=m; j++)sum+=arr[i][j];
        for(int j=1; j<=n; j++){
            while(temp*n<sum*j)temp+=arr[i][++pv];
            ans[i][j]=mp(sum*j+arr[i][pv]*n*pv-temp*n, arr[i][pv]*n);
        }
    }

    for(int i=1; i<n; i++){
        pll minn=mp(llinf, 1ll);
        int temp;
        for(int j=1; j<=n; j++){
            if(!ch[j]&&ans[j][i]<minn){
                temp=j;
                minn=ans[j][i];
            }
        }
        ch[temp]=true;
        pr[i]=temp;
        printf("%lld %lld\n", minn.F, minn.S);
    }
    for(int i=1; i<n; i++)printf("%d ", pr[i]);
    for(int i=1; i<=n; i++){
        if(!ch[i])printf("%d", i);
    }
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
naan.cpp:19:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int j=1; j<=m; j++)scanf("%lld", &arr[i][j]);
                                ~~~~~^~~~~~~~~~~~~~~~~~~~
naan.cpp:40:17: warning: 'temp' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ch[temp]=true;
         ~~~~~~~~^~~~~

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