akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define taskname "VirtualACM"
using namespace std;

int ans = 0;

void cut(int v, string &s)
{
    int cnt[1000], check[1000];
    int num = 0;
    for (char c = 'a'; c <= 'z'; ++c) check[c] = cnt[c] = 0;
    for (int i = 0; i < v; ++i) ++cnt[s[i]];
    for (int i = v; i < s.size(); ++i) ++check[s[i]];
    for (char c = 'a'; c <= 'z'; ++c)
        if (cnt[c] && check[c]) ++num;
    ans = max(ans, num);
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);   cout.tie(nullptr);
    if (ifstream("test.inp"))
    {
        freopen("test.inp", "r", stdin);
        #ifdef CHECKING
            freopen(taskname".out", "w", stdout);
        #else
            freopen("test.out", "w", stdout);
        #endif // CHECKING
    }
    else if (ifstream(taskname".inp"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }

    int n;  cin >> n;
    string s;   cin >> s;
    for (int i = 1; i < n; ++i) cut(i, s);
    cout << ans;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i < b; i++)


bool sort_by(pi c, pi d){
	return c.S < d.S;
}

int main() {
	int n, m1;
	cin >> n >> m1;
	int a, b;
	map<int, vi> m;
	REP(i, 0, m1){
		cin >> a >> b;
		m[a].PB(b);
	}
	string ans = "IMPOSSIBLE";
	
	for(auto it=m[1].begin(); it != m[1].end(); it++){
		for(auto it1=m[*it].begin(); it1 != m[*it].end(); it1++){
			if(*it1 == n){
				ans = "POSSIBLE";
			}
		}
	}
		
	cout << ans;

}


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

int main() {
	int n,k,s;
	cin>>n>>k>>s;
	for(int i=1;i<=k;i++) printf("%d ",s);
	if(s==1) s++;
	else s--;
	for(int i=k+1;i<=n;i++) printf("%d ",s);
}


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

int	main() {
	int N;
	cin >>N;
	vector<int> D(N+1, 0);
	for (int i=1; i<=N; i++)
		cin >>D.at(i);
	sort(D.begin(), D.end());
	for (int i=0; i<=N; i +=2)
		D.at(i) =-D.at(i);
	int a=D.at(1);
	for (int i=2; i<=N; i++)
		a=min(a, abs(D.at(i)-D.at(i-2)));
	a=min(a, 12-abs(D.at(N))+12-abs(D.at(N-1)));
	cout <<a <<endl;
	return 0;
};


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

int main(){
  int n;
  int flag = 1;
  int a[205];
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a[i];
    if(a[i] % 2) flag = 0;
  }
  if(!flag){
    cout << 0 << endl;
    return 0;
  }else{
    int sum = 0;
    while(flag){
      sum++;
      for(int i = 0; i < n; i++){
        a[i] /= 2;
        if(a[i] % 2) flag = 0;
      }
    }
    cout << sum << endl;
  }
  return 0;
}


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

using namespace std;

int main()
{
	unordered_map<int, int> mp;
	
	int n, m;

	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		int x;
	
		cin >> x;
	
		mp[x]++;
	}	
	
	cin >> m;
	
	bool ans = 1;
	
	for (int i = 0; i < m; i++)
	{
		int x;
	
		cin >> x;
	
		if (!mp[x])
			ans = 0;
		else
			mp[x]--;
	}
	
	if (ans)
		puts("YES");
	else
		puts("NO");
}

Measured memory_bytes: 8648
#include <stdio.h>
#define SIZE 10
struct Ink{
	int x, y;
	int size;
};

void fill(int x, int y, int paper[SIZE][SIZE]){
	if(x < 0 || x >= SIZE){return;}
      	if(y < 0 || y >= SIZE){return;}
	paper[x][y]++;	
}

void drop(struct Ink ink, int paper[SIZE][SIZE]){
	int i,j;
	switch(ink.size){
		case 1:
			fill(ink.x  , ink.y  , paper);
			fill(ink.x  , ink.y-1, paper);
			fill(ink.x-1, ink.y  , paper);
			fill(ink.x  , ink.y+1, paper);
			fill(ink.x+1, ink.y  , paper);
		break;
		case 2:
			for(i = -1; i <= 1; i++){
				for(j = -1; j <= 1; j++){
					fill(ink.x + i, ink.y + j, paper);
				}
			}
		break;
		case 3:	
			fill(ink.x  , ink.y-2, paper);
			fill(ink.x-2, ink.y  , paper);
			fill(ink.x  , ink.y+2, paper);
			fill(ink.x+2, ink.y  , paper);
			for(i = -1; i <= 1; i++){
				for(j = -1; j <= 1; j++){
					fill(ink.x + i, ink.y + j, paper);
				}
			}
		break;
	}	
}

void printResult(int paper[SIZE][SIZE]){
	int i,j;
	int bCounter = 0;
	int max = 0;
	for(i = 0; i < SIZE; i++){
		for(j = 0; j < SIZE; j++){
			if(!paper[i][j]){
				bCounter++;
			}else if(paper[i][j] > max){
				max = paper[i][j];
			}
		}
	}
	printf("%d\n%d\n", bCounter, max);
}

int main(void){
	char str[6];
	int paper[SIZE][SIZE];
	int i,j;
	struct Ink ink;
	for(i = 0; i < SIZE; i++){
		for(j = 0; j < SIZE; j++){
			paper[i][j] = 0;
		}
	}
	while(1){
		if( scanf("%s",str) == EOF){break;}
		ink.x = str[0] - '0';
		ink.y = str[2] - '0';
		ink.size = str[4] - '0';
		drop(ink,paper);
	}
	printResult(paper);
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstring>
using namespace std;

int main(void){
    int n;
    cin >> n;
    char *s, *k;
    s = new char[10001];
    cin >> s;
    k = s;
    while(*k){
        *k += n;
        if(*k > 'Z') *k -=26;
        k++;
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define MOD 998244353
#define rep(i, n) for (int i=0; i<(n); i++)
using namespace std;
using ll = long long;

int mod_pow(int n, int p, int m) {
    if (p == 0) return 1;
    if (p % 2 == 0) {
        int t = mod_pow(n, p / 2, m);
        return (t * t) % m;
    }
    return n * mod_pow(n, p - 1, m) % m;
}
int modinv(int a, int mod) {
    return mod_pow(a, mod - 2, mod);
}

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
signed main() {
    COMinit();
    int n, a, b, k;
    int ans = 0;
    cin >> n >> a >> b >> k;
    rep(red, n + 1) {
        if (red * a > k || red * a + n * b < k) continue;
        if ((k - red * a) % b != 0) continue;
        int blue = (k - red * a) / b;
        //cout << red << " " << blue << endl;
        ans += COM(n, red) * COM(n, blue) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

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

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
        #define eprintf(...) 42
#endif

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

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

  vi a(n);
  rep(i, n){
    cin >> a[i];
  }

  vl s(n+1);
  rep(i, n){
    s[i+1] = s[i] + a[i];
  }

  vl v[2];
  repi(i, 1, n+1) repi(j, i, n+1){
    v[1].pb(s[j]-s[i-1]); 
  }

  ll ans = 0, t = 0;
  for(int i = 60; i >= 0; i--){
    for(ll x : v[(t+1)%2]){
      if(x>>i & 1){
        v[t%2].pb(x);
      }
    }

    if(v[t%2].size() >= k){
      ans += 1LL<<i;
      t++;
    }

    v[t%2].clear();
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6132
#include <iostream>

int a,b;
int main(){
	while(std::cin >> a >> b){
		if(a<b) std::cout << "a < b" << std::endl;
		else if(a>b) std::cout << "a > b" << std::endl;
		else std::cout << "a == b" << std::endl;
	}
}


Measured memory_bytes: 3036
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9 + 7;

int main(void) {

    int A,B; cin>>A>>B;
    int ans=0;
    for (int i = 0; i < 2; ++i) {
        if(A>B){
            ans += A;
            A--;
        }else{
            ans += B;
            B--;
        }
    }

    cout<<ans<<endl;

}


Measured memory_bytes: 256
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

max_v=sum(V)
dp=[[0]+[float("inf")]*(max_v) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,max_v+1):
        if j-V[i]>=0:
            dp[i][j]=min(dp[i-1][j-V[i]]+W[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
#     print(dp[i])

for i in range(max_v+1):
    if dp[n][i]<=w:
        ans=i
print(ans)

Measured memory_bytes: 384824
#include <bits/stdc++.h>
using namespace std;
 
typedef long double LD;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define REP(i,n) for (ll i = 0; i < n; i++)
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REPD(i,n) for (ll i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (ll i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<ll,ll> mll;
typedef vector<ll> vll;
typedef vector<vll> vvl;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t--)
#define SZ(x) ((int)(x).size())
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))
#define i1(x) cin>>x
#define i2(x,n) cin>>x>>n
#define o1(x) cout<<x
#define o2(x,n) cout<<x<<n
int main(){
    string s ;
    i1(s);
    if(s[2]==s[3] && s[4]==s[5])
        o1("Yes");
    else 
        o1("No");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 最小公倍数
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}*/

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

	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	a--, b--, c--, d--;
	string s;
	cin >> s;

	// a から c へ
	// b から d へ

	// 右にいるやつを先に行かせる
	// もし、右にいるやつより左にいるやつの方が奥に行きたいなら
	// ...となっている場所が必要

	bool ok = true;

	if (c < d) {
		// 普通に解く
		int cnt = 0;
		Rep(i, a, c) {
			if (s[i] == '#') cnt++;
			else cnt = 0;
			if (cnt >= 2) {
				ok = false;
				break;
			}
		}

		Rep(i, b, d) {
			if (s[i] == '#') cnt++;
			else cnt = 0;
			if (cnt >= 2) {
				ok = false;
				break;
			}
		}
	}
	else {
		// 追い抜かす
		ok = false;
		int cnt = 0;
		Rep(i, b - 1, d + 2) {
			if (s[i] == '.') cnt++;
			else cnt = 0;
			if (cnt >= 3) {
				ok = true;
				break;
			}
		}
	}

	if (ok) cout << "Yes" << endl;
	else cout << "No" << endl;


	return 0;
}


Measured memory_bytes: 592
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>

using namespace std;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;

ll n = 0, m = 0, k = 0, ans = 0, sum = 0, cnt = 0, temp = 0;
string s;
bool flag;

//--------------------------------------------------------------------------

#define MAX 110000

#define INF 11111111111111111
#define NOT 0
#define VIS 1
#define COMP 2

ll stt[MAX];
ll mini[MAX];
vector<pll> edge[MAX];
priority_queue<pll, vector<pll>, greater<pll>> pq;

void dijkstra(ll start) {
  pll min;
  FOR(i, 1, n + 1) {
	stt[i] = NOT;
	mini[i] = INF;
  }
  mini[start] = 0;
  pq.push(make_pair(0, start));

  while (!pq.empty()) {
	min = pq.top();
	pq.pop();
	m = min.second;
	stt[m] = COMP;

	if (mini[m] < min.first) continue;

	FOR(i, 0, edge[m].size()) {
	  k = edge[m][i].first;
	  if (stt[k] != COMP) {
		if (edge[m][i].second + mini[m] < mini[k]) {
		  mini[k] = edge[m][i].second + mini[m];
		  stt[k] = VIS;
		  pq.push(make_pair(mini[k], k));
		}
	  }
	}
  }

}

int main(void) {
  ll a, b, c, q, x, y;
  cin >> n;

  FOR(i, 0, n - 1) {
	cin >> a >> b >> c;
	edge[a].push_back(make_pair(b, c));
	edge[b].push_back(make_pair(a, c));
  }

  cin >> q >> k;

  dijkstra(k);

  FOR(i, 0, q) {
	cin >> x >> y;
	cout << mini[x] + mini[y] << endl;
  }

  return 0;
}

Measured memory_bytes: 12272
// A.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include<vector>
#include<string>
using namespace std;

int main()
{
    string s, t;
    int cnt = 0;
    cin >> s >> t;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] != t[i])cnt++;
    }
    cout << cnt << endl;
}



Measured memory_bytes: 3912
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		long Inf = (long) 1e18;
		long[] ma = new long[N + 1];
		for(int i=0;i<=N;i++) ma[i] = - Inf;
		Pair[] P = new Pair[N];
		for(int i=0;i<N;i++) P[i] = new Pair(i, D[i]);
		
		Array.Sort(P, (p, q) => -1 * (p.D.CompareTo(q.D)));
		var SH = new SkewHeap<Pair>();
		int[] cnt = new int[N];
		long tD = 0;
		var h = new HashSet<int>();
		for(int i=0;i<K;i++){
			tD += D[P[i].Idx];
			cnt[T[P[i].Idx]]++;
			h.Add(T[P[i].Idx]);
			if(cnt[T[P[i].Idx]] > 1){
				SH.Push(P[i]);
			}
		}
		
		ma[h.Count] = tD;
		for(int i=K;i<N;i++){
			int nt = T[P[i].Idx];
			if(h.Contains(nt)) continue;
			if(SH.Count == 0) continue;
			h.Add(nt);
			var p = SH.Top; SH.Pop();
			tD -= p.D;
			tD += P[i].D;
			ma[h.Count] = Math.Max(tD, ma[h.Count]);
		}
		
		long ans = - Inf;
		for(int i=0;i<=N;i++){
			if(ma[i] == - Inf) continue;
			ans = Math.Max(ans, (long)i * (long) i + ma[i]);
		}
		
		Console.WriteLine(ans);
	}
	
	class Pair :IComparable<Pair> {
		public int Idx;
		public long D;
		public Pair(int idx, long d){
			Idx = idx; D = d;
		}
		public int CompareTo(Pair t) {
			return D.CompareTo(t.D);
		}
		
	}
	
	int N,K;
	int[] T;
	long[] D;
	public Sol(){
		var d = ria();
		N = d[0]; K = d[1];
		T = new int[N];
		D = new long[N];
		for(int i=0;i<N;i++){
			d = ria();
			T[i] = d[0] - 1; D[i] = d[1];
		}
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


class SkewHeap<T> where T:IComparable<T>{
	public int Count{
		get{return cnt;}
		private set{cnt=value;}
	}
	
	public SkewHeap(){
		root=null;
		this.Count=0;
	}
	
	public void Push(T v){
		NodeSH<T> p=new NodeSH<T>(v);
		root=NodeSH<T>.Meld(root,p);
		this.Count++;
	}
	
	public void Pop(){
		if(root==null)return;
		root=NodeSH<T>.Meld(root.L,root.R);
		this.Count--;
	}
	
	public T Top{
		get{return root.Val;}
	}
	
	int cnt;
	NodeSH<T> root;
	
	class NodeSH<S> where S : IComparable<S> {
		public NodeSH<S> L, R;
		public S Val;

		public NodeSH(S v){
			Val = v;
			L = null; R = null;
		}
		public static NodeSH<S> Meld(NodeSH<S> a, NodeSH<S> b){
			if(a == null)return b;
			if (b == null) return a;
			if (a.Val.CompareTo(b.Val) > 0) swap(ref a, ref b);
			a.R = Meld(a.R, b);
			swap(ref a.L, ref a.R);
			return a;
		}

		static void swap<U>(ref U x, ref U y) {
			U t = x; x = y; y = t;
		}
	}
}


Measured memory_bytes: 27964
#include <iostream>
#include <climits>
#include <cmath>
#include <vector>
#define endl '\n'
#define ll long long

// a > b
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}

using namespace std;

int main(void)
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    ll N, X; cin >> N >> X;
    vector<ll> vec; vec.push_back(X);
    for(int i = 0; i < N; i++) { ll temp; cin >> temp; vec.push_back(temp); }
    
    sort(vec.begin(), vec.end());
    
    ll ret = vec[1] - vec[0];
    for(int i = 1; i < N; i++)
    {
        ll dis = vec[i + 1] - vec[i];
        if(ret < dis) swap(ret, dis);
        ret = gcd(ret, dis);
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
#define int long long

int a[100], dp[100][100];
int calc(int l, int r, int n){
	int ans = 0;
	for(int i = l;i <= r;i++)ans += dp[n][i];
	return ans;
}

void init(){
	dp[0][0] = 1;
	for(int i = 1;i <= 51;i++){
		dp[i][0] = 1;
		for(int j = 1;j <= 51;j++)
		dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
	}
}

signed main(){
	init();
	int n, l, r;
	scanf("%lld%lld%lld", &n, &l, &r);
	for(int i = 1;i <= n;i++)scanf("%lld", &a[i]);
	sort(a+1, a+n+1, greater<int>());
	
	int sum = 0, s1 = 0, s2 = 0;
	double d = 0;
	for(int i = 1;i <= n;i++){
		if(i <= l)sum += a[i];
		if(a[i] > a[l])s1++;
		if(a[i] == a[l])s2++;
	}
	printf("%lf\n", (double)sum/l);
	
	if(s1 == 0){
		int ans = calc(l, r, s2);
		printf("%lld\n", ans);
	}else{
		printf("%lld\n", dp[s2][l-s1]);
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
T = [int(_) for _ in input().split()]
for i in range(N - 1):
    T[i + 1] += T[i]
T = [0] + T
V = [int(_) for _ in input().split()]
V = V
vel = [min(i / 2, T[-1] - i / 2) for i in range(2 * T[-1] + 1)]
for i in range(N):
    for j in range(2 * T[-1] + 1):
        vel[j] = min(vel[j],
                     max(V[i], -j / 2 + T[i] + V[i], j / 2 - T[i + 1] + V[i]))
print((2 * sum(vel) - vel[0] - vel[-1]) / 4)


Measured memory_bytes: 50268
#include "bits/stdc++.h"

typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define REP(i,n) for (int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
 
using namespace std;
int a[1000000] = {0};
signed main(){
    
    
//s[i-6] == '' && s[i-5] == '' && s[i-4] == '' && s[i-3] == '' && s[i-2] == '' && s[i-1] == '' && s[i] == ''

    string s;
    cin >> s;

    for(int i = s.size() - 1;i >= 0;i--){
        if(s[i-6] == 'd' && s[i-5] == 'r' && s[i-4] == 'e' && s[i-3] == 'a' && s[i-2] == 'm' && s[i-1] == 'e' && s[i] == 'r'){
            i -= 6;cerr << "a";
        }else if(s[i-5] == 'e' && s[i-4] == 'r' && s[i-3] == 'a' && s[i-2] == 's' && s[i-1] == 'e' && s[i] == 'r'){
            i -= 5;cerr << "b";
        }else if(s[i-4] == 'd' && s[i-3] == 'r' && s[i-2] == 'e' && s[i-1] == 'a' && s[i] == 'm'){
            i -= 4;cerr << "c";
        }else if(s[i-4] == 'e' && s[i-3] == 'r' && s[i-2] == 'a' && s[i-1] == 's' && s[i] == 'e'){
            i -= 4;cerr << "d";
        }else{
            cout << "NO";
            return 0;
        }
      cerr << i;
    }
    cout << "YES";

    return 0;
}


Measured memory_bytes: 512
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input();a=[0]*2
for i in range(2,n+1):
 a+=[a[i-1]+s[i-2:i].count("AC")]
for _ in range(q):
 l,r=map(int,input().split())
 print(a[r]-a[l])

Measured memory_bytes: 7996
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647
#define dset(n) cout << fixed << setprecision(n)

void yes() {
  cout << "Yes";
}

void no() {
  cout << "No";
}

int main() {
  kyun;
  in6 n;
  cin >> n;
  vi high(n);
  rep(i,n) cin >> high[i];
  bool ans = 1;
  repa(i,1,n) {
    if(high[i-1] <= high[i]) continue;
    else if(high[i-1]-1 == high[i]) high[i]++;
    else ans = 0;
  }
  if(ans) yes();
  else no();
  hinata;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) ll((a).size())
#define out(a) cout<<(a)<<endl;
const int inf=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;


int main(){
  ll n,k;cin>>n>>k;
  
  vll a(n);
  
  rep(i,0,n){
    cin>>a[i];
  }
  ll l=0,r=MOD;
  while(r-l>1){
    ll m=(l+r)/2,cnt=0;
    rep(i,0,n){
      cnt+=a[i]/m;
      if(a[i]%m==0){
        cnt--;
      }
    }
    if(cnt>k){
      l=m;
    }
    else r=m;
  }
  cout<<r<<endl;
}



Measured memory_bytes: 4844
#include<bits/stdc++.h>
#define FOR0(i,n) for(int i=0;i<n;i++)
#define FOR1(i,n) for(ll i=1;i<=n;i++)
#define FORl(i,l,n) for(ll i=l;i<n;i++)
using namespace std;
#define pi pair<ll, ll>
#define pb push_back
#define ll long long
#define ld long double	
#define ff first
#define ss second
#define mp make_pair
#define mst0(x) memset(x,0,sizeof(x));
#define vi vector<ll>
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define sp <<" "<<
#define intmax 1e18
// double power(double num, double g) {
// 	if (g == 0)return 1;
// 	if (g % 2 == 1)return (num * power((num * num), g / 2));
// 	return power( (num * num) , g / 2);
// }

int main(){
	ll n;
	cin >> n;
	ll a[n];
	unordered_map<ll, ll> arr1, arr2;
	FOR0(i, n) cin >> a[i];
	FOR0(i, n){
		if (i + 1 > a[i]) arr1[i + 1 - a[i]]++;
		arr2[i + 1 + a[i]]++;
	}
	ll ans = 0;
	for (auto x : arr1){
		if (arr2.find(x.first)!=arr2.end()){
			ans += x.ss * arr2[x.first];
		}
	}
	cout << ans << endl;
}




Measured memory_bytes: 17588
//小数点以下　cout << fixed << setprecision(10) << num << endl;
//桁数はlog10(mid)でやれ　log(mid)/log(10)はWA
//long*long<0で判定するな
//開区間と閉区間
//アルファベットが何番目かは x=s[i]-'a'
//bfsはmain()内で　rep(i,h)rep(j,w)rep(i,4)でバグ
//切り上げ：(a+(b-1))/b
//32bit以上は 1ull<<j
// map 初期値0 for(auto itr=mp.begin();itr!=mp.end();++itr) itr->fi itr->se で全探索
// for(auto u:mp) u.fi u.se も可能
//n個のgcd,lcmは一つずつみて更新していく
//大きな数を扱うときは素因数分解した形で持っておく
// (l/a[i]) = l*powmod(a[i],MOD-2)%MOD;
//auto itr=lower_bound(ALL(a),key) a[itr-a.begin()]
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional> //operator[]
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

struct Unionfind{
    vector<int> data;
    Unionfind(int size): data(size, -1) {}
    bool unite(int x, int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            if( data[y] < data[x] ) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x!=y;
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    int root(int x){
        return (data[x] < 0)? x : data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};

signed main(){
    int n,m,k;
    cin >> n >> m >> k;
    Unionfind fr(n);
    vector<vector<int>> to(n);
    rep(i,m){
        int a,b; cin >> a >> b;
        a--; b--;
        fr.unite(a,b);
        to[a].pb(b);
        to[b].pb(a);
    }
    vector<int> ans(n,0);
    rep(i,n){
        ans[i]=fr.size(i)-to[i].size();
    }
    rep(i,k){
        int c,d; cin >> c >> d;
        c--; d--;
        if(fr.same(c,d)){
            ans[c]--;
            ans[d]--;
        }
    }
    rep(i,n) cout << ans[i]-1 <<" ";
}


Measured memory_bytes: 7416
c[1100000],n=1e6;main(i,j){for(i=2;i*i<n;++i)for(j=i;!c[i]&&j<n;c[j+=i]=1);for(i=1;++i<n;c[i]=c[i-1]+!c[i]);for(;~scanf("%d",&n);printf("%d\n",c[n]));}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };  // i<4:4way i<8:8way
int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

ll a[100005];

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n;
    cin >> n ;
    ll ans = 0;
    rep(i,n){
        int t;
        cin >> t;
        a[t]++;
        ans += t;
    }
    int q;
    cin >> q;
    rep(i,q){
        ll b,c;
        cin >> b >> c;
        ans -= a[b] * b;
        ans += a[b] * c;
        a[c] += a[b];
        a[b] = 0;
        cout << ans << endl;
    }
}

Measured memory_bytes: 4384
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n;
  cin >> n;
  vector<string> s(n);
  vector<i64> t(n);
  for (i64 i = 0; i < n; i++)
    cin >> s[i] >> t[i];
  string x;
  cin >> x;
  i64 ans = 0;
  bool ok = false;
  for (i64 i = 0; i < n; i++)
    if (ok)
      ans += t[i];
    else if (s[i] == x)
      ok = true;
  cout << ans << endl;

  return 0;
}


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

typedef long long ll;

ll i,j,m,n;

bool solve(){
	cin >> n >> m;
	if(n+m==0)return false;
	long double ans = 1000000;
	for(i=0;i<=n;i++){
		ll a,b;
		a = i;
		b = n - i;
		ans = min(ans,(long double)abs(m-sqrt(a*a+b*b)));
	}
	cout << setprecision(25) << ans << endl;
	return true;

}

int main(){
	while(solve());
	return 0;

}


Measured memory_bytes: 3248
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args) {

		BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in));
		String str="";
		StringTokenizer stk;
		int[] k1=new int[2];
		int i=0;
		try {
			while(true) {
				str = bfr.readLine();
				if(str==null) {
					System.exit(0);
				}
				stk=new StringTokenizer(str," ");
				while(stk.hasMoreTokens()) {
					k1[i]=Integer.parseInt(stk.nextToken());
					i++;
				}
				i=0;
				System.out.println(""+(k1[0]+k1[1])/2);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}


Measured memory_bytes: 24428
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string S;
  cin>>S;
  int x=0;
  int y=0;
  rep(i,S.size()){
    if((i+1)%2!=0){
      if(S[i]=='0') y++;
      else if(S[i]=='1')x++;
    }
    else if((i+1)%2==0){
      if(S[i]=='0') x++;
      else if(S[i]=='1')y++;
    }
  }
  cout<<min(x,y)<<endl;
  return 0;
}

Measured memory_bytes: 512
int main(int argc ,const char *argv[])
{
    int n,x,a;
    while(1){
        scanf("%d %d",&n,&x);
        if(n==0&&x==0){
            break;
        }else{
            a=0;
            for(int i=1;i<=n-2;i++){
                for(int j=i+1;j<=n-1;j++){
                    for(int k=j+1;k<=n;k++){
                        if(i+j+k==x){
                            a++;
                        }
                    }
                }
            }
            printf("%d\n",a);
        }
    }
    return 0;
}


Measured memory_bytes: 2144
#include <iostream>
#include <cstdio>

#define MX 2010
#define MOD 1000000007

int A, B, C[MX][MX], s[MX][MX];

int main(){
	for(int i = 0; i < MX; i++){
		C[i][0] = s[i][0] = 1;
		for(int j = 1; j <= i; j++)
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
		for(int j = 1; j < MX; j++)
			s[i][j] = (s[i][j-1] + C[i][j]) % MOD;
		for(int j = 1; j < MX; j++)
			s[i][j] = (s[i][j-1] + s[i][j]) % MOD;
	}
	scanf("%d%d", &A, &B);
	int ans = 0;
	for(int t = 1; t <= A+1; t++){
		ans++;
		for(int a = 1; a < std::min(t, B); a++)
			ans = (ans + 1ll * C[B-1][a] * s[a-1][t-a-1] % MOD) % MOD;		
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 31872
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void){

    char N[11];
    int S_n = 0,i,Oridinal_N;

    scanf("%s",N);

    Oridinal_N = atoi(N);
    for(i = 0;i < strlen(N);i++){
        S_n += (int)(N[i] - '0');
    }

    if(Oridinal_N%S_n == 0){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const double PI = 3.14159265358979323846264338327950;
const LL MOD = 1000000007;

#define PrintLn(X) cout << X << endl
#define Loop(n) for(int loop_ = n; loop_; --loop_)
#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define For(i, a, b) for(int i = a; i < (int)(b); ++i)

int d[10 + '0'] = {0};
int f(int num){
	char numStr[10];
	sprintf(numStr, "%d", num);
	int len = strlen(numStr);
	Rep(i, len){
		if(d[numStr[i]]){
			return 0;
		}
	}
	return 1;
}

int main(void)
{
	int N, K;
	cin >> N >> K;
	Rep(i, K){
		char D;
		cin >> D;
		d[D] = 1;
	}
	For(i, N, 100000){
		if(f(i)){
			PrintLn(i);
			break;
		}
	}
	return 0;
}


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

int main() {
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);
    int d[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            d[i][j]=1e6;
        }
    }
    for(int i=0;i<n;i++){
        d[i][i]=0;
    }
    for(int i=0;i<n-1;i++){
        d[i][i+1]=1;
        d[i+1][i]=1;
    }
    d[x-1][y-1]=1;
    d[y-1][x-1]=1;
    int count[n];
    for(int i=0;i<n;i++) count[i]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            d[i][j]=min({abs(j-i),abs(x-1-i)+abs(y-1-j)+1,abs(y-1-i)+abs(x-1-j)+1});
            count[d[i][j]]++;
        }
    }
    for(int i=1;i<n;i++){
        count[i]=count[i]/2;
        printf("%d\n",count[i]);
    }
}

Measured memory_bytes: 15872
#include<iostream>
using namespace std;
int main(){
long n;
cin>>n;
if(n % 500 == 0){
	cout<<1000*(n/500);
}
else
{
	long a = n % 500;
	long b = a % 5;	
	//if(b < 5)
	long c = n/500;
	long q = c*1000;
	long d = a/5;
	long w = d*5;
	cout<<q+w;
}

}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.NoSuchElementException;

	
public class Main{
	
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		FastScanner sc=new FastScanner();
		int N=sc.nextInt();
		BigInteger prd=BigInteger.valueOf(1);
		for (int i=0;i<N;++i) {
			long A=sc.nextLong();
			if (A==0) prd=BigInteger.ZERO;
			if (prd.equals(BigInteger.valueOf(-1))) continue;
			prd=prd.multiply(BigInteger.valueOf(A));
			if (prd.compareTo(BigInteger.valueOf((long)1e18))==1) {
				prd=BigInteger.valueOf(-1);
			}
		}
		System.out.println(prd);
	}
	
	void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    
    public double nextDouble() { return Double.parseDouble(next());}
}


Measured memory_bytes: 47948
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")

    /*
    ||||||||||||||||||||||||||||||||||||||||||||||||
       |      |||         |      ||||    ||||  |   |
      | |     |   |      | |     |   |  |      |   |
     |   |    |    |    |   |    |   |  |      |   |
    |||||||   |    |   |||||||   |||     |||   |||||
    |     |   |   |    |     |   | |        |  |   |
    |     |   |||      |     |   |  ||  ||||   |   |
    ||||||||||||||||||||||||||||||||||||||||||||||||

    */
    using namespace std;
    //#include "testlib.h"
    #define ff first
    #define ss second
    #define mp make_pair
    #define all(v) v.begin(),v.end()
    #define int long long
    #define ll long long
    #define M 1000000007
    #define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
    #define GCD(m,n) __gcd(m,n)
    #define LCM(m,n) m*(n/GCD(m,n))
    #define mii  map<ll ,ll >
    #define msi  map<string,ll >
    #define mis  map<ll int, string>
    #define rep(a,b)    for(ll i=a;i<b;i++)
    #define rep0(n)    for(ll i=0;i<n;i++)
    #define repi(i,a,b) for(ll i=a;i<b;i++)
    #define pb push_back
    #define vi vector<ll>
    #define mp make_pair
    #define vs vector<string>
    #define ppb pop_back
    #define endl '\n'
    #define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define r0 return 0;
    #define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
    #define FORE(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
    #define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
    #define input freopen("input.txt", "r", stdin);
    #define Set(a, s) 4(a, s, sizeof (a))
    #define FOR repi
    #define pii pair<int,int>
    #define REVERSE(v) reverse(ALL(v))
    #define display(x) trav(a,x) cout<<a<<" ";cout<<endl
    #define debug cerr<<"bhau"<<endl
    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        std::cerr << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
 
    //#define float long double
    ll max(ll a, ll b) { return (a > b)? a : b;}
    int min(int a, int b) { return (a < b)? a : b;}


     int solve()
     {  
        int n,k;cin>>n>>k;
        vi a(n);
        inputarr(a,n);
        vector<bool> dp(k+1,0);
        for(int stones=0;stones<=k;stones++){
            for(auto x: a){
                if(stones>=x&&!dp[stones-x])
                {
                    dp[stones]=1;break;
                }
            }
        }
        string ans=(dp[k])?"First":"Second";
        cout<<ans;

        r0   
     }
    signed main()
    {   
        asdf
      
        int t=1;
        //cin>>t;
        while(t--)
        {
            solve();
        }     
        
}

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

using namespace std;

#define f first
#define s second


struct node{
    int x, y;
};


const long long MOD = 1e9+7;
const int N = 1003;
vector<pair<int,int > > G[N][N];
vector<pair<int,int>>vec = {{1,0},{0,1}};
vector<pair<int,int>>top;
char grid[N][N];
bool odw[N][N];
int h,w;
long long dp[N][N];



bool valid(int y, int x){

    return y >=0 && y < h && x >= 0 && x < w && grid[y][x] != '#'; 
}


void dfs(pair<int,int>start){

    odw[start.f][start.s] = true;

    for (auto next:G[start.f][start.s]){

        if (!odw[next.f][next.s]) dfs({next});
    }

    top.push_back(start);
}




int main(){
    ios_base::sync_with_stdio(0);

    cin >> h >> w;

    for (int i=0; i<h; i++){
        for (int j=0; j<w; j++){
            cin >> grid[i][j];
        }
    }

    for (int i=0; i<h; i++){
        for (int j=0; j<w; j++){
            for (auto next:vec){

                if (valid(i+next.f, j+next.s)){

                    G[i][j].push_back({i+next.f, j+next.s});
                }
            }
        }
    }

    dfs({0,0});

    reverse(top.begin(),top.end());


    dp[0][0] = 1;
    for (auto next:top){
        for (auto som:G[next.f][next.s]){

            dp[som.f][som.s] += dp[next.f][next.s];
            //cout << "Dodaje do " << som.f << " " << som.s << " " << dp[next.f][next.s] << "\n";
            dp[som.f][som.s] %= MOD;
        }
    }


    cout << dp[h-1][w-1];
}

Measured memory_bytes: 72936
#include "bits/stdc++.h"
using namespace std;

#define ll long long
#define str string

ll MOD = 1000000007, INFL = 1ll << 60, INF = 1 << 30;
ll A[10000000] = {}, X[1000000] = {};
int dy[] = { 0, 0, 1, -1 }, dx[] = { 1, -1, 0, 0 };
vector <ll> v;
ll a = INFL, b = 0, c = 0, n = 0, sum = 0, max = INF;
str S;
bool an = false,bn = false;

int findDigits(int n) {
	int i = 0;
	while (n > 0) {

		X[i] = n % 10;
		n /= 10;
		i++;
	}
	return i;
}


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//Code Line
	cin >> n;
	findDigits(n);
	if (X[0] + X[1] * 10 <= 12 && X[0] + X[1] * 10 > 0)an = true;
	if (X[2] + X[3] * 10 <= 12 && X[2] + X[3] * 10 > 0)bn = true;
	if (an && bn)cout << "AMBIGUOUS" << endl;
	else if (an)cout << "YYMM" << endl;
	else if (bn)cout << "MMYY" << endl;
	else cout << "NA" << endl;
	cin >> n;
	//Code Line
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#ifndef U_L_LONG
typedef unsigned long long ULLONG;
#endif
#ifndef L_LONG
typedef long long LLONG;
#endif
template <class _T> static _T tp_abs(const _T& a) {
	//	usage:  tp_abs<type name>(a);
	return ((a < 0) ? (a * -1) : a);
}
template <class _T> static _T tp_min(_T a, _T b) {
	return a < b ? a : b;
}
template <class _T> static _T tp_max(_T a, _T b) {
	return a > b ? a : b;
}
template<class _T> static void get1int(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void get2int(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void get3int(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}
static void getstring(char* buff) {
	if (scanf(" %s", buff) < 0) {
		printf("getstr error!\n");
	}
}

static void ABC094C_ManyMedians();

#if 1
int main()
{
	ABC094C_ManyMedians();
	fflush(stdout);
	return 0;
}
#endif

class ABC094C_set
{
public:
	int orgIdx = 0;
	int value = 0;
	int med = 0;

	static bool sort_asc_val(const ABC094C_set& a, const ABC094C_set& b) {
		return a.value < b.value;
	}
	static bool sort_asc_idx(const ABC094C_set& a, const ABC094C_set& b) {
		return a.orgIdx < b.orgIdx;
	}
};
static void ABC094C_ManyMedians()
{
	int N;
	get1int(N);

	auto dset = new ABC094C_set[N + 1];

	for (int i = 0; i < N; i++) {
		get1int(dset[i].value);
		dset[i].orgIdx = i;
	}

	std::sort(dset, dset + N, ABC094C_set::sort_asc_val);
	int partition = N / 2;
	for (int i = 0; i < N; i++) {
		if (i < partition) {
			dset[i].med = dset[partition].value;
		}
		else {
			dset[i].med = dset[partition - 1].value;
		}
	}
	std::sort(dset, dset + N, ABC094C_set::sort_asc_idx);
	for (int i = 0; i < N; i++) {
		printf("%d\n", dset[i].med);
	}
		
	delete dset;
}


Measured memory_bytes: 4480
//Author - Rahil Malhotra
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int32_t main()
{
    IOS;
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int sum=0;
    for(int i=1;i<n;i++)
    {
        sum+=max(0ll,arr[i-1]-arr[i]);
        arr[i]=max(arr[i],arr[i-1]);
    }
    print(sum);
}

Measured memory_bytes: 5200
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define REP(i, a) for (ll i(0), _##i(a); i < _##i; ++i)
#define FOR(i, a, b) for (ll i(a), _##i(b); i <= _##i; ++i)

#ifdef LOCAL
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define _FE_6(_CALL, x, ...) _CALL(x) _FE_5(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
  _NTH_ARG(__VA_ARGS__, _FE_6, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1)              \
  (MACRO, __VA_ARGS__)
#define watch(x) cerr << "\033[1;32m" #x " = \033[1;34m" << (x) << "\033[0m; ";
#define debug(...)                                                             \
  cerr << "\033[2;31mLine " << __LINE__ << ": \033[0m";                        \
  FOR_EACH_MACRO(watch, __VA_ARGS__)                                           \
  cerr << endl
#else
#define debug(...)
#endif

using namespace std;

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << '{' << p.first << ", " << p.second << '}';
}

template <class T, class = decltype(begin(declval<T>())),
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
  os << '[';
  for (auto it = begin(c); it != end(c); ++it)
    os << (it == begin(c) ? "" : ", ") << *it;
  return os << ']';
}
using ll = long long;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int &x : a) cin >> x;

  const ll INF = 1ll << 62;
  vector<vector<pair<ll,ll>>> dp(n, vector<pair<ll,ll>>(n, {INF, INF}));
  function<pair<ll,ll>(int,int)> bt = [&](int l, int r) -> pair<ll,ll>{
    if (l == r) {
      return {a[l], 0};
    }
    auto &res = dp[l][r];
    if (res != make_pair(INF, INF)){
      return res;
    }
    auto go1 = bt(l + 1, r);
    auto go2 = bt(l, r - 1);
    ll x = a[l] + go1.S; 
    ll y = a[r] + go2.S;
    if (x > y){
      return res = {x, go1.F};
    } else {
      return res = {y, go2.F};
    }
  };

  auto ans = bt(0, n - 1);
  cout << ans.F - ans.S << "\n";
}

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

  int T = 1;
  // cin >> T;
  while (T--) {
    solve();
  }
}


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

#define ff first
#define ss second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define check(x) cout << #x << " : " << (x) << endl
#define inf LLONG_MAX
#define all(v) v.begin(),v.end() 
#define allr(v) v.rbegin(),v.rend() 
//#define endl '\n'  
#define mod 998244353
typedef  long long ll; 
typedef  unsigned long long ull; 
//using u64 = uint64_t; 
//using u128 = __uint128_t;
typedef vector< ll > edge; 
typedef pair< ll , bool > mypair;
typedef priority_queue <ll> max_heap;
typedef priority_queue <ll, vector<ll>, greater<ll> > min_heap;
const ll N=1e5+20;
std::vector<pair<ll,bool>> v[N];
ll n;
std::vector<bool> color(N,0),visited(N,0);
void dfs(ll k, bool clr)
{
	visited[k]=1;
	color[k]=clr;
	for(auto i:v[k])
	{
		if(visited[i.ff]==0)
		{
			if(i.ss) dfs(i.ff,!clr);
			else dfs(i.ff,clr);
		}
	}
}
int main()
{
	boost;
	cin>>n;
	for(ll i=0;i<n-1;i++)
	{
		ll x,y,w;
		cin>>x>>y>>w;
		v[x].pb(mp(y,w%2));
		v[y].pb(mp(x,w%2));
	}
	dfs(1,0);
	for(ll i=1;i<=n;i++) cout<<color[i]<<endl;

	return 0;
}

Measured memory_bytes: 9472