JOI2014春day4

Constellation 2

わからん(0点)
辺の交差判定(N^4),ある頂点がある三角形に含まれるか判定(N^4)
N^2とか出来るわけ無いだろ!いい加減にしろ!

Kanji

わからん
クエリ毎によくわからない辺のうち1以下の個数の辺を使うことがわかる。どれを使えばよいか送ればむこうで適当に最短路取って経路復元すればいいので使う辺のid(0~4+使わないで6通り)を2進数にして送ってむこうで6進数になおせば(2^160>6^60なのでいける)40点
あとはわからん
Messenger別解みたいなSleepを妄想した

//Anna.cpp
#include "Annalib.h"
#include <cstdio>
#define rep(i,n) for(int i=0;i<(n);++i)
typedef long long ll;
static int prev[300][300];//iからの最短路でjの直前
static ll inf=((ll)1e+18)*3+1;
static ll d[300][300];
static int edgeid[300][300];
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
	ll send=0;
	rep(i,N) rep(j,N){
		if(i!=j) d[i][j]=inf;
		prev[i][j]=-1;
		edgeid[i][j]=-1;
	}
	rep(i,M){
		d[A[i]][B[i]]=C[i];
		prev[A[i]][B[i]]=A[i];
		edgeid[A[i]][B[i]]=i;
	}
	rep(h,N) rep(i,N) rep(j,N){
		if(d[i][j]>d[i][h]+d[h][j]){	//i->jでhを通る
			d[i][j]=d[i][h]+d[h][j];
			int tmp=j;
			while(true){
				prev[i][tmp]=prev[h][tmp];
				tmp=prev[h][tmp];
				if(tmp==h) break;
			}
		}
	}
/*	rep(i,N){
		rep(j,N){
			printf("%d ",prev[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	rep(i,N){
		rep(j,N){
			printf("%lld ",d[i][j]);
		}
		printf("\n");
	}
*/
	int digit[160]={};
	rep(i,Q){
		int ss=S[i],tt=T[i],ans=5;
		while(ss!=tt){
			rep(j,K) if(edgeid[prev[ss][tt]][tt]==U[j]) ans=j;
			tt=prev[ss][tt];
		}
		rep(j,160) digit[j]*=6;
		digit[0]+=ans;
		rep(j,159){
			digit[j+1]+=digit[j]/2;
			digit[j]%=2;
		}
	}
	rep(i,160) Tap(digit[159-i]);
//	printf("anna");
}
//Bruno.cpp
#include "Brunolib.h"
#include <cstdio>
#define rep(i,n) for(int i=0;i<(n);++i)
typedef long long ll;
static int prev[300][300];
static ll inf=((ll)1e+18)*3+1;
static ll d[300][300];
static int edgeid[300][300];
static int vc[300];

void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
	rep(i,N) rep(j,N){
		if(i!=j) d[i][j]=inf;
		prev[i][j]=-1;
		edgeid[i][j]=-1;
	}
	rep(i,M){
		if(C[i]==-1) C[i]=inf;
		d[A[i]][B[i]]=C[i];
		prev[A[i]][B[i]]=A[i];
		edgeid[A[i]][B[i]]=i;
	}
	rep(h,N) rep(i,N) rep(j,N){
		if(d[i][j]>d[i][h]+d[h][j]){	//i->jでhを通る
			d[i][j]=d[i][h]+d[h][j];
			int tmp=j;
			while(true){
				prev[i][tmp]=prev[h][tmp];
				tmp=prev[h][tmp];
				if(tmp==h) break;
			}
		}
	}
	int digit[160]={};
	rep(i,L){
		rep(j,160) digit[j]*=2;
		digit[0]+=X[i];
		rep(j,159){
			digit[j+1]+=digit[j]/6;
			digit[j]%=6;
		}
	}
	rep(i,Q){
		int ans=digit[Q-1-i];
		int ss=S[i],tt=T[i],cnt=0;
		if(ans==5){
			while(ss!=tt){
				vc[cnt]=edgeid[prev[ss][tt]][tt];
				cnt++;
				tt=prev[ss][tt];
			}
		}else{
			int tmp=B[U[ans]];
			while(tmp!=tt){
				vc[cnt]=edgeid[prev[tmp][tt]][tt];
				cnt++;
				tt=prev[tmp][tt];
			}
			vc[cnt]=U[ans];
			cnt++;
			tmp=A[U[ans]];
			while(ss!=tmp){
				vc[cnt]=edgeid[prev[ss][tmp]][tmp];
				cnt++;
				tmp=prev[ss][tmp];
			}
		}
		rep(j,cnt) Answer(vc[cnt-j-1]);
		Answer(-1);
	}
}

#include ＜vector＞ にエラー吐かれたりして配列に書きなおしたけどなんだったんだ
上記の部分半角にするとはてなブログが勝手にコメントアウトする闇

Straps

ほんとうにやるだけ(というと実装量が多いみたいだけど実装量も0です) どうせ勘違いしてるんだろうと思ってSubmitしたら通った 代表なら5分で解きそう

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define ALL(c) (c).begin(),(c).end()
typedef pair<int,int> P;
int dp[2001][2001],inf=2000000001;
P st[2000];
int main(){
	int n;
	scanf("%d",&n);
	rep(i,n){
		int a,b;
		scanf("%d%d",&a,&b);
		st[i]=P(a,b);
	}
	sort(st,st+n,greater<P>());
	rep(i,n+1) rep(j,n+1) dp[i][j]=-inf;
	dp[0][1]=0;
	rep(i,n){
		rep(j,n+1){
			dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
			if(j>0) dp[i+1][min(j+st[i].first-1,n)]=max(dp[i+1][min(j+st[i].first-1,n)],dp[i][j]+st[i].second);
		}
	}
	int ans=-inf;
	rep(i,n+1) ans=max(dp[n][i],ans);
	printf("%d\n",ans);
	return 0;
}