Submission #152289

#	Time	Username	Problem	Language	Result	Execution time	Memory
152289		username	Naan (JOI19_naan)	C++14	100 / 100	578 ms	102616 KiB

naan

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define int int64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define f first
#define s second
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)

const int maxn=2009;
int n,l,p[maxn],v[maxn][maxn];
pii c[maxn][maxn];
bitset<maxn>us;

main(){
	IOS;
	cin>>n>>l;
	REP(i,0,n){
		v[i][0]=0;
		REP(j,0,l)cin>>v[i][j+1],v[i][j+1]+=v[i][j];
	}
	REP(i,0,n){
		int ptr=0;
		REP(j,1,n){
			while(v[i][ptr+1]*n<=v[i][l]*j)++ptr;
			int k=(v[i][ptr+1]-v[i][ptr])*n;
			c[i][j]={k*ptr+v[i][l]*j-v[i][ptr]*n,k};
		}
	}
	REP(i,1,n){
		int opt=-1;
		REP(j,0,n){
			if(us[j])continue;
			if(opt<0||(__int128)c[j][i].f*c[opt][i].s<(__int128)c[opt][i].f*c[j][i].s)opt=j;
		}
		p[i]=opt;
		us[opt]=1;
		cout<<c[opt][i].f<<" "<<c[opt][i].s<<endl;
	}
	REP(i,1,n)cout<<p[i]+1<<" ";
	REP(i,0,n)if(!us[i])cout<<i+1<<endl;
}

Compilation message (stderr)

naan.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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