T1
#include <cstdio>
#include <algorithm>
#define f(x, y, z) for(int x = (y); x <= (z); ++x)
const bool _av[18] = {1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0};
inline bool av(int x){
return x > 17 || _av[x];
}
int n, m, dp[100086], mdp[100086];
struct e{int val, pos;} E[100086];
inline bool operator <(const e &x, const e &y){return x.pos < y.pos;}
int main(){
scanf("%d%d", &n, &m);
f(i, 1, n) scanf("%d%d", &E[i].val, &E[i].pos);
std::sort(E + 1, E + (n + 1));
E[0].pos = 0;
dp[0] = mdp[0] = 0;
f(i, 1, n){
dp[i] = -2000000000;
int j = i - 1;
for(; j && (E[i].pos - E[j].pos) <= 17; --j) if(av(E[i].pos - E[j].pos) && dp[j] + E[i].val > dp[i]) dp[i] = dp[j] + E[i].val;
if(av(E[i].pos - E[j].pos) && mdp[j] + E[i].val > dp[i]) dp[i] = mdp[j] + E[i].val;
mdp[i] = std::max(mdp[i - 1], dp[i]);
}
printf("%d\n", mdp[n]);
return 0;
}T2
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define inf 1000000000
#define ll long long
#define N (n+m)*30
using namespace std;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int ans;
int T,n,m;
int a[35][35];
int f[1805][35][35];
void dp()
{
f[a[1][1]][1][1]=a[1][1]*a[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<=N;k++)
if(f[k][i][j]!=1000000)
{
int x=i+1,y=j,v=a[x][y];
f[k+v][x][y]=min(f[k+v][x][y],f[k][i][j]+v*v);
x=i,y=j+1,v=a[x][y];
f[k+v][x][y]=min(f[k+v][x][y],f[k][i][j]+v*v);
}
for(int i=1;i<=N;i++)
if(f[i][n][m]!=1000000)
ans=min(ans,(n+m-1)*f[i][n][m]-i*i);
}
int main()
{
T=read();
for(int cas=1;cas<=T;cas++)
{
//printf("Case #%d: ",cas);
ans=inf;
n=read();m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<=N;k++)
f[k][i][j]=1000000;
dp();
printf("%d\n",ans);
}
return 0;
}T3
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
#define M 16
using namespace std;
struct KSD
{
int v,len,next;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v,int len)
{
e[++cnt].v=v;
e[cnt].len=len;
e[cnt].next=head[u];
head[u]=cnt;
}
int n,m;
int f[N][M],F[N],g[M];
void dfs1(int x,int p)
{
int i,j,k,v;
for(i=head[x];i;i=e[i].next)
{
v=e[i].v;
if(v==p)continue;
dfs1(v,x);
F[x]+=F[v]+e[i].len/M;
f[x][e[i].len%M]++;
for(j=0;j<M;j++)
{
k=j+e[i].len;
F[x]+=k/M*f[v][j];
f[x][k%M]+=f[v][j];
}
}
return ;
}
void dfs2(int x,int p)
{
int i,j,k,v;
for(i=head[x];i;i=e[i].next)
{
v=e[i].v;
if(v==p)continue;
int temp=F[x]-F[v]-e[i].len/M;
for(j=0;j<M;j++)
{
k=j+e[i].len;
temp-=k/M*f[v][j];
g[k%M]=f[x][k%M]-f[v][j];
}
g[e[i].len%M]--;
F[v]+=temp+e[i].len/M;
f[v][e[i].len%M]++;
for(j=0;j<M;j++)
{
k=j+e[i].len;
F[v]+=k/M*g[j];
f[v][k%M]+=g[j];
}
dfs2(v,x);
}
}
int main()
{
int i,j,k;
int a,b,c;
scanf("%d%d",&n,&m);
for(i=1;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
dfs1(1,0);
dfs2(1,0);
for(i=1;i<=n;i++)
{
int ans=F[i]<<4;
for(j=0;j<M;j++)ans+=(j^m)*f[i][j];
printf("%d\n",ans);
}
return 0;
}t4
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <set>
#include <ctime>
#include <algorithm>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)<0?-(a):(a))
#define inf 214748364
#define pi 3.141592653589793
#define maxn 100011
using namespace std;
typedef long long ll;
vector<int > e[maxn];
int fir[maxn],nex[maxn],t[maxn],typ[maxn],q[maxn];
int con;
int n,m,qa[maxn],qb[maxn];
int root;
int bin[maxn],res[maxn];
inline void addline(int st,int en,int inpq)
{
nex[++con]=fir[st],fir[st]=con;
t[con]=en,typ[con]=2,q[con]=inpq;
nex[++con]=fir[en],fir[en]=con;
t[con]=st,typ[con]=1,q[con]=inpq;
}
inline void dfs(int p)
{
bin[p]=1;
for(int i=fir[p];i;i=nex[i])
if(bin[t[i]])
res[q[i]]=typ[i];
for(vector<int >::iterator i=e[p].begin();i!=e[p].end();++i)
dfs(*i);
bin[p]=0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
int st,en;
scanf("%d%d",&st,&en);
if(en==-1)
root=st;else
e[en].push_back(st);
}
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&qa[i],&qb[i]);
addline(qa[i],qb[i],i);
}
dfs(root);
for(int i=1;i<=m;++i)
printf("%d\n",res[i]);
return 0;
}T5
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define maxn 100001
ll a[maxn],b[maxn];
ll pre[maxn],prep[maxn];
ll n;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
for(int i=1;i<=n;++i)
scanf("%lld",&b[i]);
ll res=0;
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(ll i=1;i<=n;++i)
{
pre[i]=pre[i-1]+b[i];
prep[i]=prep[i-1]+b[i]*b[i];
}
for(ll i=n,j=n+1;i>=1;--i)
{
while(j>1&&b[j-1]>a[i])
--j;
ll m=n+1-j;
res-=m*a[i]*a[i];
res-=prep[n]-prep[j-1];
res+=2*a[i]*(pre[n]-pre[j-1]);
}
for(ll i=1,j=0;i<=n;++i)
{
while(j<n&&b[j+1]<a[i])
++j;
ll m=j;
res+=m*a[i]*a[i];
res+=prep[j];
res-=2*a[i]*pre[j];
}
double ans=res/(double )n;
printf("%.1lf\n",ans);
return 0;
}T6
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <functional>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn = 1000 + 50;
const int maxsum = 10000 + 50;
const int mo = 999983;
int f[maxn][maxsum] = {0};
int n;
bool canuse[10] = {0};
int maxvalue = 0;
long long ans = 0;
void ReadData()
{
cin >> n;
char c;
while (cin >> c)
{
canuse[c - '0'] = true;
maxvalue = max(maxvalue, c - '0');
}
}
void DP()
{
f[0][0] = 1;
for (int i = 0; i <= maxvalue; i++)
{
if (canuse[i])
{
f[1][i] = 1;
}
}
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= maxvalue * i; j++)
{
for (int k = 0; k <= maxvalue; k++)
{
if (canuse[k])
{
f[i + 1][j + k] += f[i][j];
f[i + 1][j + k] %= mo;
}
}
}
}
}
inline long long sqr(long long X)
{
return X * X;
}
void CalcAns()
{
for (int i = 0; i <= maxvalue * n; i++)
{
ans += 2 * sqr(f[n][i]);
ans %= mo;
}
int a = int(n / 2.0 - 1e-8) + 1;
int b = n >> 1;
long long A = 0;
long long B = 0;
for (int i = 0; i <= maxvalue * a; i++)
{
A += sqr(f[a][i]);
A %= mo;
}
for (int i = 0; i <= maxvalue * b; i++)
{
B += sqr(f[b][i]);
B %= mo;
}
ans = (ans + mo - A * B % mo) % mo;
}
int main()
{
ReadData();
DP();
CalcAns();
cout << ans << endl;
return 0;
}