akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(void) {
        long n,k,t,t_min;

        scanf("%ld %ld",&n,&k);

        long x[n];

        for (long i=0;i<n;i++) {
                scanf(" %ld", x+i);
        }

        long min, max;
        for (long i=0;i<=n-k;i++) {
                min = x[i];
                max = x[i+k-1];

                if (min>=0) {
                        t = max;
                }
                else if (max<=0) {
                        t = -min;
                }
                else if (min+max>=0) {
                        t = -min*2 + max;
                }
                else if (min+max<=0) {
                        t = -min + max*2;
                }

                if (i==0) t_min = t;
                else if (t<=t_min) t_min = t;
        }

        printf("%ld\n",t_min);
        return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, n, m) for (int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

typedef long long ll;

/**
 * 不安なら ll を使う.
 * 小数は double を忘れない.
 * nC2の求め方 (1/2)*n*(n-1)
 * vector<型> 変数名(要素数, 初期値)
 * pair<型, 型> 変数名
 * map<型, 型> 変数名  // 連想配列
 * priority_queue<型> 変数名  // 最大値から出てくるヒープ
 * 比較するときは型まで注意
 * 区間の計算は累積和
*/

/* ===== コーナーケースに気をつけろ ===== */

int main()
{
    int L;
    cin >> L;
    double a = (double)L / 3.0;
    printf("%.7lf\n", a * a * a);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int N=1000000;

typedef pair<int,int> pi;

//?????£??????????????±
int field[1000][1000]={0};
//??????(??°????????§?¨?)
pi im[N+1];
//?´???°????????????
bool prime[N+1];

int n,m;

//?????§???
int dp[N+1];
//????????¨???????????????????????????????´???°
int last[N+1];

int dfs(int v)
{
    if(dp[v]>=0) return dp[v];

    int ret=0;
    pi now=im[v];
    if(now.fi==999)
    {
        if(prime[v])
        {
            ret=1;
            last[v]=v;
        }
    }
    else
    {
        int t[3];
        memset(t,-1,sizeof(t));

        if(now.se>0 && field[now.fi+1][now.se-1]<=m)
            t[0]=dfs(field[now.fi+1][now.se-1]);
        if(field[now.fi+1][now.se]<=m)
            t[1]=dfs(field[now.fi+1][now.se]);
        if(now.se<1000-1 && field[now.fi+1][now.se+1]<=m)
            t[2]=dfs(field[now.fi+1][now.se+1]);

        ret=max({0,t[0],t[1],t[2]});
        rep(i,3)
        {
            if(ret==t[i]) last[v]=max(last[v],last[field[now.fi+1][now.se+i-1]]);
        }

        if(prime[v])
        {
            ++ret;
            if(ret==1) last[v]=v;
        }
    }

    return dp[v]=ret;
}

bool inline in(int x, int y)
{
    return (0<=x&&x<1000 && 0<=y&&y<1000);
}

int main()
{
    //?´???°??¨??????
    fill(prime,prime+N+1,true);
    prime[0]=prime[1]=false;
    for(int i=2; i<=N; ++i)
    {
        if(prime[i]) for(int j=2; i*j<=N; ++j) prime[i*j]=false;
    }

    //?????£???????????????
    int h=0,w=0;
    int dir=0;
    int dh[4]={0,1,0,-1}, dw[4]={1,0,-1,0};
    for(int i=N; i>0; --i)
    {
        field[h][w]=i;
        im[i]=pi(h,w);
        h+=dh[dir];
        w+=dw[dir];
        if(!in(h,w) || field[h][w]>0)
        {
            h-=dh[dir];
            w-=dw[dir];
            dir=(dir+1)%4;
            h+=dh[dir];
            w+=dw[dir];
        }
    }

    while(scanf(" %d %d", &m, &n),m|n)
    {
        memset(dp,-1,sizeof(dp));
        memset(last,0,sizeof(last));
        int ans=dfs(n);
        printf("%d %d\n", ans, last[n]);
    }
    return 0;
}

Measured memory_bytes: 23796
using System;

namespace Project
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			string s = Console.ReadLine();
			int a, b;
			string[] sar = s.Split(' ');
			a = int.Parse(sar[0]);
			b = int.Parse(sar[1]);
			int surface = a * b;
			int mawari = 2 * a + 2 * b;
			Console.WriteLine("{0} {1}", surface, mawari);
		}
	}
}

Measured memory_bytes: 8976
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  vector<int>a(n + 1, true);
  for (int i = 0; i < m; i++) {
    int t;
    cin >> t;
    a[t] = false;
  }

  vector<long long int>dp(n + 1);
  dp[0] = 1;

  for (int now = 0; now < n; now++) {
    for (int next = now + 1; next <= min(n, now + 2); next++) {
      if (a[next]) {
        dp[next] += dp[now];
        dp[next] %= 1000000007;
      }
    }
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_map>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<long long> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	long long sump;
	if (a[0] > 0) {
		sump = a[0];
//        cout << sump << endl;
	}
	else {
		sump = 1;
//        cout << sump << endl;
	}
	long long countp;
	if (a[0] > 0) {
		countp = 0;
//        cout << countp << endl;
	}
	else {
		countp = 1 - a[0];
//        cout << countp << endl;
	}
	for (int i = 1; i < n; i++) {
		if (sump * (sump + a[i]) < 0) {
			sump = sump + a[i];
//			cout << sump << endl;
//            cout << countp << endl;
		}
		else {
			countp += max(1 - (sump + a[i]), 1 + (sump + a[i]));
			sump = -(abs(sump) / sump);
//			cout << sump << endl;
//            cout << countp << endl;
		}
	}
//	cout << countp << endl;

	long long summ;
	if (a[0] < 0) {
		summ = a[0];
//        cout << summ << endl;
	}
	else {
		summ = -1;
//        cout << summ << endl;
	}
	long long countm;
	if (a[0] < 0) {
		countm = 0;
//        cout << countm << endl;
	}
	else {
		countm = 1 + a[0];
//        cout << countm << endl;
	}
	for (int i = 1; i < n; i++) {
		if (summ * (summ + a[i]) < 0) {
			summ = summ + a[i];
//			cout << summ << endl;
//            cout << countm << endl;
		}
		else {
			countm += max(1 - (summ + a[i]), 1 + (summ + a[i]));
			summ = -(abs(summ) / summ);
//			cout << summ << endl;
//            cout << countm << endl;
		}
	}
//	cout << countm << endl;
    cout << min (countp, countm) << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <math.h>
using namespace std;
struct Point {double x,y;};

void koch(int n, Point a, Point b){
    if(n==0)return;
    Point s,t,u;
    double th = M_PI*60.0/180.0;
    s.x=(2.0*a.x + 1.0*b.x)/3.0;
    s.y=(2.0*a.y + 1.0*b.y)/3.0;
    t.x=(1.0*a.x + 2.0*b.x)/3.0;
    t.y=(1.0*a.y + 2.0*b.y)/3.0;
    u.x=(t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;
    u.y=(t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;
    
    koch(n-1,a,s);
    printf("%.8f %.8f\n",s.x,s.y);
    koch(n-1,s,u);
    printf("%.8f %.8f\n",u.x,u.y);
    koch(n-1,u,t);
    printf("%.8f %.8f\n",t.x,t.y);
    koch(n-1,t,b);
};

int main(){
    Point a,b;
    int n;
    scanf("%d",&n);
    a.x=0;
    a.y=0;
    b.x=100;
    b.y=0;
    printf("%.8f %.8f\n",a.x,a.y);
    koch(n,a,b);
    printf("%.8f %.8f\n",b.x,b.y);
    
    return 0;
    
}


Measured memory_bytes: 2736
# -*- coding: utf-8 -*-


def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]

    for i in range(n - 1):
        ai, bi, ci = map(int, input().split())
        ai -= 1
        bi -= 1
        graph[ai][bi] = ci
        graph[bi][ai] = ci

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        print(dist[xi] + dist[yi])


if __name__ == '__main__':
    main()


Measured memory_bytes: 53856
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

// conversion
//------------------------------------------
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T> inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

// math
//-------------------------------------------
template <class T> inline T sqr(T x) { return x * x; }

// typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

// container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c)                                                             \
  for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

// clear memory
#define CLR(a) memset((a), 0, sizeof(a))

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                                               \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"                       \
       << " " << __FILE__ << endl;

void solve(long long N, long long L) {
  int m=10000000;
  int dec=0;
  bool flag=false;
  int sum=0;
  for(int i=1; i<N+1; i++){
    int cur = L+i-1;
    // cout<<cur<<endl;
    if(m>abs(cur)){
      dec=cur;
      m=abs(cur);
    }
    sum+=cur;
  }
  cout<<sum-dec<<endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long L;
  scanf("%lld", &L);
  solve(N, L);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
string s;
int main(){
    cin>>s;
    int i=0;
    int j=s.size()-1;
    int ans=0;
    while(i<j){
        if(s[i]!=s[j]) ans++;
        i++;
        j--;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;
#define REP(i,j,n) for(int i=j;i<n;i++)
#define rep(i,n) REP(i,0,n)


// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int ary[4];
    rep(i,4) ary[i] = 0;

    int n;
    cin >> n;
    rep(i,n)
    {
        string s;
        cin >> s;
        if (s == "AC")
        {
            ary[0]++;
        }
        else if (s=="WA")
        {
            ary[1]++;
        }
        else if (s=="TLE")
        {
            ary[2]++;
        }
        else
        {
            ary[3]++;
        }
    }
    cout << "AC x " << ary[0] << endl;
    cout << "WA x " << ary[1] << endl;
    cout << "TLE x " << ary[2] << endl;
    cout << "RE x " << ary[3] << endl;
}


Measured memory_bytes: 3652
/*
By Snickeen
*/
#include<bits/stdc++.h>
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <string>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
typedef long double ldb;
#define rep(i,a,b) for(i=a;i<b;i++)
#define repu(i,a,b) for(i=a;i<=b;i++)
#define repd(i,a,b) for(i=a;i>=b;i--)
#define repc(i,a,b,c) for(i=a;i<b;i+=c)
#define repcu(i,a,b,c) for(i=a;i<=b;i+=c)
#define repcd(i,a,b,c) for(i=a;i>=b;i-=c)
#define FIN freopen("input.in","r",stdin)
#define FOUT freopen("output.out","w",stdout)
#define CC(a) memset(a,0,sizeof(a))
#define MST(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define VI vector<int>
#define VL vector<LL>
#define VII vector<PII >
#define VLL vector<PLL >
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define pf push_front
#define FF first
#define SS second

template<typename T>inline void gn(T &x){
	x=0;T f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
template<typename T>inline void gt(T x){
	if(!x)return;
	gt(x/10);putchar(x%10+'0');
}
 
const LL MAXN=1e5+10;
LL t,n,m,ans;
LL MOD=1e9+7,inf=0x1f1f1f1f;
db eps=1e-5;

string s[111];

int main()
{
//	ios_base::sync_with_stdio(false);cin.tie(0);
	LL i,j,k,l,ca=0;
	cin>>n>>m;
	repu(i,1,n){
		cin>>s[i];
	} 
	repu(i,1,n){
		cout<<s[i]<<endl;
		cout<<s[i]<<endl;
		
	}
	return 0;
}

Measured memory_bytes: 256
// Aizu Vol-20 2001: Amida, the City of Miracle
// 2017.8.12 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

typedef struct { int h, p, q; } T;
T t[1003], *p, *e;

int cmp(T *p, T *q) { return q->h - p->h; }

int main()
{
	int n, m, a;

	while (1) {
		scanf("%d%d%d", &n, &m, &a); if (!n) break;
		for (p = t, e = p + m; p < e; p++) scanf("%d%d%d", &(p->h), &(p->p), &(p->q));
		qsort(t, m, sizeof(T), cmp);
		for (p = t, e = p + m; p < e; p++) {
			if      (p->p == a) a = p->q;
			else if (p->q == a) a = p->p;
		}
		printf("%d\n", a);
	}
	return 0;
}

Measured memory_bytes: 672
h,w = map(int,input().split())
s = [0]*h
white = 0
for i in range(h):
	s[i] =  input()
	s[i] = list(s[i])
	for j in range(w):
		if s[i][j] == '.':
			white += 1

def clear_maze(sx, sy, gx, gy, maze):

	INF = 100000000

	field_x_length = len(maze)
	field_y_length = len(maze[0])
	distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
#	distance = [[INF]*field_y_length]*field_x_length

	def bfs():
		queue = []

		queue.insert(0, (sx, sy))

		distance[sx][sy] = 0

		while len(queue):
			x, y = queue.pop()

			if x == gx and y == gy:
				break

			for i in range(0, 4):
				nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

				if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
					queue.insert(0, (nx, ny))
					distance[nx][ny] = distance[x][y] + 1

		return distance[gx][gy]
	return bfs()
if clear_maze(0, 0, h-1, w-1, s) == 100000000:
	print(-1)
else:
	print(white - clear_maze(0, 0, h-1, w-1, s) - 1)

Measured memory_bytes: 9252
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int ans = 0;
    if(s=="RRR")cout << 3<<endl;
    else if(s=="RRS" || s=="SRR")cout<<2<<endl;
    else if(s=="SSS")cout<<0<<endl;
    else cout<<1<<endl;
}

Measured memory_bytes: 3624
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
VI G[100011];
int deg[100011];
bool use[100011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N-1) {
	int x, y;
	scanf("%d%d", &x, &y);
	x--; y--;
	G[x].push_back(y);
	G[y].push_back(x);
	deg[x]++;
	deg[y]++;
    }

    VI leaf; leaf.reserve(N);
    REP (i, N) if (deg[i] == 1) {
	leaf.push_back(i);
    }

    bool yes = false;

    for (int i=0; i<(int)leaf.size(); i++) {
	int v = leaf[i];
	if (deg[v] == 0) {
	    yes = true;
	    break;
	}
	if (use[v]) {
	    continue;
	}
	use[v] = true;
	EACH (e, G[v]) if (!use[*e]) {
	    use[*e] = true;
	    EACH (f, G[*e]) if (!use[*f]) {
		deg[*f]--;
		if (deg[*f] == 1) {
		    leaf.push_back(*f);
		}
	    }
	}
    }

    puts(yes? "First": "Second");
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 6528
N = int(input())
D = list(map(int, input().split()))

mod = 998244353

from collections import Counter, deque

def solve(N,D):
    if D[0]!=0:
        return 0
    c = Counter(D)
    if c[0]>1:
        return 0
    ans = 1
    m = max(D)
    for i in range(1,m):
        if c[i]==0:
            ans = 0
            continue
        ans *= pow(c[i],c[i+1],mod)
        ans %= mod
    return ans

print(solve(N,D))

Measured memory_bytes: 19808
#include <iostream>
#include <algorithm>

using namespace std;
int main(void){
    // Your code here!
  int n;
  int a[110];
  cin>>n;
  for(int i=0; i<n; i++) cin>>a[i];
  
  sort(a,a+n,greater<int>());
  int A=0,B=0;
  for (int j=0; j<n; j++){
      if (j%2!=0) B +=a[j];
      else A+=a[j];
      
  }cout<<A-B<<endl;
}


Measured memory_bytes: 256
local n, m = io.read("*n", "*n")
local t = {}
local as, bs = {}, {}
for i = 1, n do t[i] = {} end
for i = 1, m do
  local a, b = io.read("*n", "*n")
  as[i], bs[i] = a, b
  t[a][b], t[b][a] = true, true
end

local function check(tbl)
  local reached = {true}
  for i = 2, n do reached[i] = false end
  local reachnum = 1
  local tasks = {1}
  local tasknum, done = 1, 0
  while done < tasknum do
    done = done + 1
    local idx = tasks[done]
    for k, v in pairs(tbl[idx]) do
      if v and not reached[k] then
        table.insert(tasks, k)
        reached[k] = true
        reachnum = reachnum + 1
        tasknum = tasknum + 1
      end
    end
  end
  return n == reachnum
end
local ret = 0
for i = 1, m do
  t[as[i]][bs[i]], t[bs[i]][as[i]] = false, false
  if not check(t) then ret = ret + 1 end
  t[as[i]][bs[i]], t[bs[i]][as[i]] = true, true
end
print(ret)


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>
const int maxn = 105;
using namespace std;
struct p{
    int x,y;
}a[maxn],b[maxn];
int vis[maxn];
bool cmp(p a,p b){
     if (a.y == b.y){
         return a.x < b.x;
     }
     return a.y < b.y;
}
int main(){
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    for (int i = 0; i < n; i++){ 
        scanf("%d%d",&b[i].x,&b[i].y);
    }
    sort(a, a + n,cmp);
    sort(b, b + n,cmp);
    int cnt = 0;
    for (int i = n - 1; i >= 0; i--){
        int minnx = 1e9;
        int minny = 1e9;
        int pos = -1;
        for (int j = n - 1; j >= 0; j--){
            if (!vis[j]){
                if (b[j].y > a[i].y && b[j].y <= minny)
                {
                    if (b[j].x < minnx && b[j].x > a[i].x) {
                        pos = j;
                        minnx = b[j].x;
                        minny = b[j].y;
                    }
                }
            }
        }
        if (pos != -1){
            vis[pos] = 1;
            cnt++;
        }
    }
    printf("%d\n",cnt);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <tuple>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pa;
const ll MOD = 1e9 + 7;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (int i = (l); i < (r); i++)
#define reper(i, l, r) for (int i = (r)-1; i >= (l); i--)

void init() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
}
//-----------------------------------------------------------//

int main() {
    init();
    int N,ans=0;
    cin>>N;
    vector<int> L(N);
    rep(i,N)cin>>L[i];
    sort(all(L));
    rep(i,N-2)repe(j,i+1,N-1){
    	int ok=j+1,ng=N,mid;
    	while(ng-ok>1){
    		mid=(ok+ng)/2;
    		if(abs(L[i]-L[j])<L[mid]&&L[mid]<L[i]+L[j])ok=mid;
    		else ng=mid;
    	}
    	
    	if(L[ok]<=abs(L[i]-L[j])||L[i]+L[j]<=L[ok])continue;
    	int right=ok;
    	
    	ng=j,ok=N-1;
    	while(ok-ng>1){
    		mid=(ok+ng)/2;
    		if(abs(L[i]-L[j])<L[mid]<L[i]+L[j])ok=mid;
    		else ng=mid;
    	}
    	int left=ok;
    	ans+=right-left+1;
    	//cout<<i<<j<<ans<<' '<<left<<' '<<right<<endl;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

#include <set>
#include <map>
#include <iomanip>

using namespace std;

#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define rrep(i, n) for(long long i = (long long)(n - 1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using ll = long long;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> h(n);
	rep(i, n)
	{
		cin >> h[i];
	}

	vector<vector<int>> node(n);
	rep(i, m)
	{
		int a, b;
		cin >> a >>  b;
		a--; b--;

		node[a].push_back(b);
		node[b].push_back(a);
	}

	int ans = 0;
	rep(i, n)
	{
		bool flag = true;
		for (auto d : node[i])
		{
			if (h[i] <= h[d])
			{
				flag = false;
			}
		}

		if (flag)
		{
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 8808
#include <bits/stdc++.h>
using namespace std; 

#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
int main()  
{ 
    FAST_INP;
    int n;
    cin >> n;
    int ans=0;
    for(int i=1;i<=n;i++) {
    	int a;
    	cin >> a;
    	if((i&1)&&(a&1)) ans++;
	}
	cout << ans;
    return 0;
} 

Measured memory_bytes: 3604
#include <stdio.h>
#include <stdlib.h>

void DisplayArray(int A[], int N)
{
    int i;
    for (i = 0; i < N; i++) {
        if (i) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
}

int SelectionSort(int A[], int N)
{
    int i, j, minj, tmp, count = 0;

    for (i = 0; i < N; i++) {
        minj = i;
        for (j = i; j < N; j++) {
            if (A[j] < A[minj]) {
                minj = j;
            }
        }
        if (i != minj) count++;
        tmp = A[i];
        A[i] = A[minj];
        A[minj] = tmp;
    }

    return count;
}

int main(void)
{
    int N, i, numOfExchanges;
    scanf("%d%*c", &N);
    int* A = (int*)malloc(sizeof(int) * N);

    for (i = 0; i < N; i++) scanf("%d", &A[i]);
    scanf("%*c");

    numOfExchanges = SelectionSort(A, N);
    DisplayArray(A, N);
    printf("%d\n", numOfExchanges);

    return 0;
}

Measured memory_bytes: 604
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    if (N==M){
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 22996
import java.util.*;
public class Main
{
	

  public static void main(String [] args)
  {
    Scanner sc=new Scanner(System.in);
     int S=sc.nextInt();
    int W=sc.nextInt();
    if(W>=S)
      System.out.println("unsafe");
    else
      System.out.println("safe");
  }

}


Measured memory_bytes: 27036
# 数の少ないものから消すと考える
n, k = map(int, input().split())
arr = list(map(int, input().split()))
d = {}
for a in arr:
  if a not in d:
    d[a] = 1
  else:
    d[a] += 1

t = len(d)

d = list(sorted(d.items(), key = lambda x : x[1]))
if t <= k:
  print(0)
else:
  count = 0
  for di in d[:t-k]:
    count += di[1]
  print(count)

Measured memory_bytes: 38964
# -*- coding: utf-8 -*-
"""
C - All Green
https://beta.atcoder.jp/contests/abc104/tasks/abc104_c

"""
import sys
from sys import stdin
input = stdin.readline


from itertools import combinations
from math import ceil

def solve(D, G, scores):
    def pick_max(comb):
        a = [i*100 for i in range(D, 0, -1)]
        for c in comb:
            a.remove(c)
        return a[0] if a else None


    ans = float('inf')
    points = [100 * p for p in range(1, D+1)]

    for d in range(D+1):
        for comb in combinations(points, d):
            score = 0
            pick = 0
            for p in comb:
                score += (p * scores[p][0]) + scores[p][1]
                pick += scores[p][0]
            if score < G:
                ad = pick_max(comb)
                if ad:
                    n = ceil((G - score) / ad)
                    if n >= scores[ad][0]:
                        pick = float('inf')
                    else:
                        pick += n
                else:
                    pick = float('inf')
            ans = min(ans, pick)
    return ans


def main(args):
    D, G = map(int, input().split())

    scores = {}
    for i in range(1, D+1):
        p, c = map(int, input().split())
        scores[i*100] = [p, c]
    ans = solve(D, G, scores)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3188
// 2019/07/03 Tazoe

#include <iostream>
using namespace std;

int main()
{
	int N;
	cin >> N;

	int cnt = 0;
	int sta = 0;

	for(int i=0; i<N; i++){
		char C;
		cin >> C;

		if(sta==1){
			if(C=='O'){
				;
			}
			else{
				cnt++;
				sta = 0;
			}
		}
		else if(sta==2){
			if(C=='O'){
				cnt++;
				sta = 0;
			}
			else{
				;
			}
		}
		else{
			if(C=='O'){
				sta = 1;
			}
			else{
				sta = 2;
			}
		}
	}

	cout << cnt << endl;

	return 0;
}



Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 11451419
int main(){
    ll n,ans=INF;
    cin>>n;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            string p=to_string(n/i),q=to_string(i);
            ll hoge=max(p.length(),q.length());
            ans=min(hoge,ans);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>

int main() {
	long long N; std::cin >> N;
	std::vector<long long>A(N + 1);
	std::vector<long long>B(N);
	for (auto& r : A)
		std::cin >> r;
	for (auto& r : B)
		std::cin >> r;
	long long ans = 0;
	for (int i = 0; i < N; ++i) {
		if (A[i] + A[i + 1] <= B[i]) {
			ans += A[i] + A[i + 1];
			A[i + 1] = 0;
		}
		else if (A[i] <= B[i] && A[i] + A[i + 1] > B[i]) {
			ans += B[i];
			A[i + 1] -= B[i] - A[i];
		}
		else {
			ans += B[i];
		}

	}
	std::cout << ans << std::endl;
	
}


Measured memory_bytes: 4752
N = int(input())
L = list(map(int, input().split()))

ans = 0

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    for k in range(j + 1, N):
      ii = L[i]
      jj = L[j]
      kk = L[k]
      if ii == jj: continue
      if jj == kk: continue
      if kk == ii: continue
      if ii + jj <= kk: continue
      if jj + kk <= ii: continue
      if kk + ii <= jj: continue
      ans += 1

print(ans)

Measured memory_bytes: 68076
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;

const int INF = (int)1e9;

typedef pair<int, int> P;

int h, w, sx = 0, sy = 0, gx, gy, d[55][55],
dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
vector<string>hw;

int bfs() {
	queue<P> que;
	gx = h - 1, gy = w - 1;
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++) d[i][j] = INF;

	que.push(P(sx, sy));
	d[sx][sy] = 0;

	while (que.size()) {
		P p = que.front(); que.pop();
		if (p.first == gx && p.second == gy) break;

		for (int i = 0; i < 4; i++) {
			int nx = p.first + dx[i], ny = p.second + dy[i];

			if (0 <= nx && nx < h && 0 <= ny && ny < w
				&& hw[nx][ny] != '#' && d[nx][ny] == INF) {
				que.push(P(nx, ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
	}
	return d[gx][gy];
}

int main() {
	cin >> h >> w;
	hw.resize(h);
	for (auto&& x : hw) {
		cin >> x;
	}

	int white = -1;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (hw[i][j] == '.') white++;
		}
	}
	int res = bfs();
	cout << ((white - res >= 0) ? (white - res) : -1) << endl;

	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split(" "))

MOD = (10**9) + 7


def dSum(s, e):
    s -= 1
    _s = s * (s + 1) // 2
    _e = e * (e + 1) // 2
    return _e - _s


ans = 0
for i in range(k, n + 1):
    # _sum = dSum(n - i - 1, n) - dSum(0, i - 1) + 1
    ans += dSum(i, n) - dSum(0, n - i) + 1

print((ans + 1) % MOD)


Measured memory_bytes: 9152
#include <bits/stdc++.h>
using namespace std;
#define pr(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()
#define mod 1000000007 // ((a- b)% mod+ mod)% mod

void solve() {
        int n, k; scanf("%d%d", &n, &k);
        vector<int> v, csum(n+ 1);

        for (int i= 0; i< n; i++) {
                int x; scanf("%d", &x);
                x++;
                v.push_back(x);
        }

        for (int i= 1; i<= n; i++) csum[i]= csum[i- 1]+ v[i- 1];

        double an= 0;

        for (int i= 1; i<= n- k+ 1; i++) {
                an= max(an, (double)csum[i+ k- 1]- csum[i- 1]);
        }
        an/= 2;
        printf("%0.10f", an);
}

int32_t main(){
//ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int T= 1;
        //cin >> T;
        while ( T-- ) {
                solve();
        }
return 0;
}


Measured memory_bytes: 5104
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    int C[4] = {0,0,0,0};
    for (int i = 0; i < N; i++){
        string S;
        cin >> S;
        if(S=="AC")C[0]++;
        else if(S=="WA")C[1]++;
        else if(S=="TLE")C[2]++;
        else C[3]++;
    }
    cout << "AC x " << C[0] << endl;
    cout << "WA x " << C[1] << endl;
    cout << "TLE x " << C[2] << endl;
    cout << "RE x " << C[3] << endl;
}

Measured memory_bytes: 3572
#include <iostream>
#include <algorithm>
using namespace std;
int chk[10],N;
int main()
{
	for(int i=0; i<3; i++)
	{
	cin >> N;
	chk[N]++;
	}
	
	if(chk[5]==2&&chk[7]==1)
	cout << "YES\n";
	else 
	cout << "NO\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main(){
    string S;
    //Sを定義
    cin >> S;
    //標準入力
    string ans = "yes";
    //出力用の文字列変数ansを定義
    for(int i = 0; i < S.length()-1; i++){ //S.length()-1;末尾の文字を基準にチェックする必要はないため
        for(int  j = i + 1; j < S.length(); j++){ //j = i + 1; チェックされる文字はチェックする文字の1つあとにしたいため
        if(S[i] == S[j]){
            ans = "no"; 
                //被ったのでnoを出力
            } 
        }
    }
    cout << ans << endl; 
    //結果を出力
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        int count = 0;
        for(int i=0; i<s.length(); i++) {
            if(s.charAt(i) != t.charAt(i)) count++;
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 41208
#include <bits/stdc++.h>

typedef long long ll;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)

ll mod=1e9+7;

using namespace std;


ll inputValue(){
	ll a;
	cin >> a;
	return a;
};

void inputArray(int * p, ll a){
	rep(i, a){
		cin >> p[i];
	}
};

template<typename T>
void inputVector(vector<T>& p, ll a){
	rep(i, a){
		T input;
		cin >> input;
		p.emplace_back(input);
	}
}


template <typename T>
void output(T a) {
	cout << a << "\n";
}



int main(int argc, const char * argv[]) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll n,a,b;
	cin >> n >> a>> b;

	cout << min<ll>(n*a,b) << endl;

}


Measured memory_bytes: 256
<?php

function chmin(&$a, $b) {
    if ($a > $b) {
        $a = $b;
    }
}

function chmax(&$a, $b) {
    if ($a < $b) {
        $a = $b;
    }
}

fscanf(STDIN, "%d", $n);
$h = explode(' ', trim(fgets(STDIN)));

$dp = array_fill(0, $n, PHP_INT_MAX);
$dp[0] = 0;
$dp[1] = abs($h[1] - $h[0]);

for ($i = 2; $i < $n; ++$i) {

    chmin($dp[$i], $dp[$i - 1] + abs($h[$i] - $h[$i - 1]));

    chmin($dp[$i], $dp[$i - 2] + abs($h[$i] - $h[$i - 2]));
}

echo $dp[$n - 1];


Measured memory_bytes: 16884
#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll> 
#define pii pair<int, int> 
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

using namespace std;

ll MOD = 1e9+7;

ll pwr(ll x, ll y) {
	ll res = 1;
	x = x%MOD;
	while (y > 0) {
		if (y&1) res = (res*x)%MOD;

		y = y>>1;
		x = (x*x)%MOD;
	}
	return res;
}

inline ll addmod(ll a, ll b){
	return ((a+b)%MOD);
}

inline ll mulmod(ll a, ll b){
	return ((a*b)%MOD);
}

class BIT {
	int *bit;
	int N;

public:
	void update(int x, int val) {
		int ind = x;
		while (ind <= N) {
			bit[ind] += val;
			ind += (ind & (-ind));
		}
	}

	BIT(int ar[], int n) {
		bit = new int[n+1];
		N = n+1;
		for (int i = 1; i < N; i++) bit[i] = 0;
		for (int i = 1; i < N; i++) update(i, ar[i-1]);
	}

	int getSum(int x) {
		if (x < 0) return 0;

		int ind = x+1;
		int sum = 0;
		while (ind > 0) {
			sum += bit[ind];
			ind = (ind & (ind-1));
		}
		return sum;
	}

	int getValue(int x) {
		return getSum(x) - getSum(x-1);
	}

	void changeElem(int x, int val) {
		update(x+1, val-getValue(x));
	}
};

int bsh(int val, int ar[], int n) {		// return ind such that val >= ar[ind] and val < ar[ind+1]
	int a = 0, b = n - 1, c = (a+b)/2;
	if (val < ar[0]) return -1;
	if (val >= ar[b]) return b;

	while (!(val >= ar[c] && val < ar[c+1])) {
		if (val < ar[c]) b = c;
		else {
			if (b-a == 1 && c == a) a = b;
			else a = c;
		}
		c = (a+b)/2;
	}
	return c;
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n;
	ll a[n], ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a+n, greater<int>());
	ans = a[0];
	for (int i = 2; i < n; i++) {
		ans += a[i/2];
	}
	cout << ans << endl;
}



Measured memory_bytes: 5212
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
void solve(){
    int k,a,b;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++){
        if(i%k==0) {cout<<"OK";return;}
    }
    cout<<"NG";return;
}
int  main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
    //cin>>t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const int INF = 1e9;

struct Edge{
  int to, cap, cost, rev;
  Edge(int to_=0, int cap_ = 0, int cost_ = 0, int rev_ = 0)
	:to(to_), cap(cap_), cost(cost_), rev(rev_){}
};

const int MAX_V = 200*200*2;
int A, B, K;
int V;
vector<Edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V]; //??´??????????????¨???

void add_edge(int from, int to, int cap, int cost){
  G[from].push_back(Edge(to, cap, cost, G[to].size()));
  G[to].push_back(Edge(from, 0, -cost, G[from].size()-1));
}

// ?§????s, ??????t, ?????????f ???????°??????¨?????? ?????¨??????????????°-1
int min_cost_flow(int s, int t){
  int res = 0, i;
  for(i=0;i<min(A,B);++i){
	fill(dist, dist+V, INF);
	dist[s] = 0;
	bool update = true;
	while(update){
	  update = false;
	  for(int v=0;v<V;++v){
		if(dist[v] == INF) continue;
		for(int i=0;i<G[v].size();++i){
		  Edge& e = G[v][i];
		  if(e.cap > 0 && dist[v] + e.cost < dist[e.to]){
			dist[e.to] = dist[v] + e.cost;
			prevv[e.to] = v;
			preve[e.to] = i;
			update = true;
		  }
		}
	  }
	}

	if(dist[t] == INF) return 0;

	int d = 1;
	for(int v=t;v!=s;v=prevv[v])
	  d = min(d, G[prevv[v]][preve[v]].cap);

	res += d * dist[t];
	for(int v=t;v!=s;v=prevv[v]){
	  Edge& e = G[prevv[v]][preve[v]];
	  e.cap -= d;
	  G[v][e.rev].cap += d;
	}
	if(res > K) break;
  }
  return i;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  cin >> A >> B >> K;
  int S = 0, T = A+B+A*B+1;
  V = A+B+A*B+2;
  int ans = 0;
  VS as(A), bs(B);
  REP(i,A) cin >> as[i];
  REP(i,B) cin >> bs[i];
  

	REP(i,MAX_V) G[i].clear();
	FOR(i,1,A+1) add_edge(S,i,1,0);
	FOR(i,1,B+1) add_edge(A+i,T,1,0);
	REP(i,A){
	  REP(j,B){
		int t = A+B+i*B+j+1;
		add_edge(1+i,t,1,as[i][j]-'0');
	  }
	}
	REP(j,B){
	  REP(i,A){
		int t = A+B+i*B+j+1;
		add_edge(t,A+1+j,1,bs[j][i]-'0');
	  }
	}
	int c = min_cost_flow(S,T);

  cout << c << endl;
  return 0;
}

Measured memory_bytes: 9504
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
using ll = long long;
const ll MOD = 1000000007;

int main() {
	ll N, a, b;
	cin >> N;

	vector<pair<ll, ll>> VP(N);
	vector<ll> scr(2 * N);
	ll LS = 0, RS = 0;
	for (int i = 0;i < N;i++) {
		cin >> a >> b;
		LS += a;
		RS += b;
		VP[i] = { a,b };
		scr[i * 2] = a;
		scr[i * 2 + 1] = b;
	}
	sort(all(scr));

	ll C, CR = 0, CRR, ans = min(LS, RS);
	for (int i = 0;i < N;i++)CR += scr[i];
	CRR = CR;
	for (int i = 0;i < N;i++) {
		tie(a, b) = VP[i];
		if (a > b)swap(a, b);
		C = scr[N - 1];
		if (a < C) {
			if (b > C)CR += b - C;
		}
		else {
			CR += a - C;
			C = scr[N - 2];
			if (b > C) {
				CR += b - C;
			}
		}
		ans = min(ans, CR);
		CR = CRR;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

#include <cstdio>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

string s[50];
bool checked[50][50] = { false };

/*================================================
	Dijkstra
================================================*/
#define COST_TYPE int
#define NMAX (100001)
#define INF (100000000)
vector<pair<COST_TYPE, int> > G[NMAX];
COST_TYPE cost[NMAX];
bool done[NMAX] = { false };

void dijkstra(int root)
{
	priority_queue<pair<COST_TYPE, int>, vector<pair<COST_TYPE, int> >, greater<pair<COST_TYPE, int> > > PQ;
	pair<COST_TYPE, int> current;	/* first: cost, second: index */
	COST_TYPE next_cost;
	int current_index, next_index;

	rep(i, NMAX) {
		done[i] = false;
		cost[i] = INF;
	}

	cost[root] = 0;
	PQ.push(make_pair(0, root));

	while (!PQ.empty()) {
		current = PQ.top();
		PQ.pop();

		current_index = current.second;

		if (done[current_index]) continue;
		done[current_index] = true;

		rep(i, G[current_index].size()) {
			next_index = G[current_index][i].second;
			next_cost = G[current_index][i].first;

			if ((!done[next_index])
				&& (cost[next_index] > cost[current_index] + (COST_TYPE)next_cost)) {
				cost[next_index] = cost[current_index] + (COST_TYPE)next_cost;
				PQ.push(make_pair(cost[next_index], next_index));
			}
		}
	}
}

int main()
{
	int H, W;
	int shortest;
	int black = 0;

	cin >> H >> W;
	rep(i, H) cin >> s[i];

	rep(i, H) {
		rep(j, W) {
			if (s[i][j] == '#') black++;

			if (i != H - 1 && s[i + 1][j] == '.') {
				G[W * i + j].push_back(make_pair(1, W * i + j + W));
				G[W * i + j + W].push_back(make_pair(1, W * i + j));
			}

			if (j != W - 1 && s[i][j + 1] == '.') {
				G[W * i + j].push_back(make_pair(1, W * i + j + 1));
				G[W * i + j + 1].push_back(make_pair(1, W * i + j));
			}
		}
	}

	dijkstra(0);
	shortest = cost[H * W - 1];

	if (shortest == INF) cout << -1 << endl;
	else cout << H * W - black - shortest - 1 << endl;
	
	return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;



int main(){
  int n;
  cin >> n;
  vector<vector<pair<int,int>>> g(n);
  for(int i=0;i<n-1;++i){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(make_pair(b,i));
    g[b].push_back(make_pair(a,i));
  }

  queue<pair<int,int>> que;
  vector<int> dist(n,-1);
  dist[0]=0;
  que.push(make_pair(0,-1));
  vector<int> color(n-1,-1);
  map<int,int>mp;

  while(!que.empty()){
    auto p=que.front();
    que.pop();
    int c=p.second;
    int v=p.first;
    int col=1;
    if(col==c)++col;
    for(auto nv : g[v]){
      if(dist[nv.first]!=-1) continue;

      dist[nv.first]=dist[v]+1;
      que.push(make_pair(nv.first,col));
      color[nv.second]=col;
      mp[col]++;
      col++;
      if(col==c)++col;
    }
  }
  cout << mp.size() << endl;
  for(auto v : color) cout << v << endl;

  return 0;
}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
#include<string>
using namespace std;
int main(void){
    string S;
    long long Q;
    cin>>S>>Q;
  	int re=0;
    for(long long i=0;i<Q;i++){
        int T;
        cin>>T;
        if(T==1){
          if(re==0){
             re=1;
          }
          else if(re==1){
            re=0;
          }
        }
        if(T==2){
            int F;
            char C;
            cin>>F>>C;
            if(F==1){
              if(re==1){
                  S+=C;
                }
              else{
              	S.insert(S.begin(),C);
              }
            }
            if(F==2){
              if(re==0){
                S+=C;
              }
              if(re==1){
                S.insert(S.begin(),C);
              }
            }
        }
    }
    if(re==1){
        reverse(S.begin(),S.end());
    }
    cout<<S<<endl;
}


Measured memory_bytes: 900
n = int(raw_input())

dice = [[0 for i in range(6)] for j in range(n)]
for i in range(n):
    dice[i] = map(int, raw_input().split())
 
def rolling(inst, dice):
    if inst == 'E':
        dice[5], dice[2], dice[0], dice[3] = dice[2], dice[0], dice[3], dice[5]
    elif inst == 'W':
        dice[5], dice[3], dice[0], dice[2] = dice[3], dice[0], dice[2], dice[5]
    elif inst == 'N':
        dice[5], dice[4], dice[0], dice[1] = dice[4], dice[0], dice[1], dice[5]
    elif inst == 'S':
        dice[5], dice[1], dice[0], dice[4] = dice[1], dice[0], dice[4], dice[5]
 
def dice_matching(dice1, dice2):
    if dice1[1] == dice2[1]:
        for i in range(4):
            if dice1 == dice2:
                return 1
                break
            rolling('E', dice2)
        return 0
    else:
        return 0
        
flag = 0
for i in range(n):
    for j in range(i+1, n):
        count = 0
        while(1):
            if dice_matching(dice[i], dice[j]) == 1:
                flag = 1
                print 'No'
                break
            else:
                if count < 3:
                    rolling('N', dice[j])
                    count += 1
                elif 7 > count and count >= 3:
                    if count == 3:
                        rolling('E', dice[j])
                    rolling('N', dice[j])
                    count += 1
                else:
                    break
        if flag ==1:
            break
    if flag == 1:
        break
if flag == 0:
    print 'Yes'

Measured memory_bytes: 6464
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

const ll MAXN = 200005;

// fac: n!のmod
// finv: 1/n!のmod
// inv: 1/nのmod
vll fac(MAXN), finv(MAXN), inv(MAXN);

void COMinit() {
  fac.at(0) = fac.at(1) = 1;
  finv.at(0) = finv.at(1) = 1;
  inv.at(1) = 1;
  rep(i, 2, MAXN) {
    fac.at(i) = fac.at(i-1) * i % MOD;
    inv.at(i) = MOD - inv.at(MOD%i) * (MOD / i) % MOD;
    finv.at(i) = finv.at(i-1) * inv.at(i) % MOD;
  }
}

ll COM(ll n, ll k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac.at(n) * (finv.at(k) * finv.at(n-k) % MOD) % MOD;
}

int main() {
  ll n; cin >> n;
  COMinit();
  vll use(n, -1), a(n+1);;
  ll li, ri;
  REP(i, n+1) {
    cin >> a.at(i);
    if (use.at(a.at(i)-1) == -1) use.at(a.at(i)-1) = i;
    else {li = use.at(a.at(i)-1); ri = i;}
  }
  REP(i, n+1) {
    if (i==0) cout << n << endl;
    else {
      cout << (COM(n+1, i+1) - COM(n-ri+li, i) + MOD) % MOD << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 7424
#include <string>
#include <vector>
#include <iostream>

int main() {
  std::vector<std::string> v;

  size_t n, l;
  std::cin >> n >> l;

  for( size_t i = 0; i < n; ++i ) {
    std::string s;
    for( size_t j = 0; j < l; ++j ) {
      char c;
      std::cin >> c;
      s.push_back(c);
    }
    v.push_back(s);
  }

  std::sort(v.begin(), v.end());
  for( auto s : v ) {
    std::cout << s;
  }
  std::cout << std::endl;
}

Measured memory_bytes: 3128